***LeetCode 42. Trapping Rain Water

本文主要是介绍***LeetCode 42. Trapping Rain Water，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/trapping-rain-water/

最初思路是，用一个栈来存height，如果发现height[i] >= 栈顶 就计算一部分面积，时间复杂度似乎是O(n)

然后发现最后部分很难处理，比如 4 2 3。。然后没有过，，这个在考虑下 。。

很神奇的做法：

从两头向中间扫描，找当前的第二高的地方。然后求小面积：

题解

http://www.xuebuyuan.com/1586534.html

class Solution {
public:int trap(vector<int>& height) {int sech = 0, ret=0;int left = 0, right = height.size()-1;while ( left < right ) {if(height[left] < height[right] ) {sech = max( sech, height[left] );ret += sech - height[left];left ++;} else {sech = max( sech, height[right] );ret += sech - height[right];right --;}}return ret;}
};

Python代码：

class Solution(object):def trap(self, height):left = 0sech = 0;ret = 0right = len(height)-1while( left < right ) :if height[left] < height[right]:sech = max(sech, height[left])ret += sech - height[left]left += 1else :sech = max(sech, height[right])ret += sech - height[right];right -= 1return ret

感觉思路正常的做法： 找mountain  然后两个mountain之间，min(montain)-height[i]求和

感觉这样不是很容易写，，，不过也是O(n)

这篇关于***LeetCode 42. Trapping Rain Water的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---