[C++]LeetCode: 131 Trapping Rain Water (双边扫描)

题目：

Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Thanks Marcosfor contributing this image!

Answer 1:

复杂度：O(N), 空间需要一个长度为n的数组，复杂度也是O(N)

Attention:

1.max / min是c++的关键字，不能用来做变量名。

2.leftmax[0] = 0 ,左边是没有凭栏储水的。要先对数组赋值，再计算当前最大值（将当前bar的高度考虑进去）

<span style="font-size:14px;">//记录每一个bar左边最大高度for(int i = 0; i < n; i++){container[i] = maxheight;maxheight = max(maxheight, A[i]);}</span>3. 计算rightmax时，要重置maxheight.<span style="font-size:14px;">maxheight = 0;</span>AC Code：<span style="font-size:14px;">class Solution {public:int trap(int A[], int n) {int maxheight = 0;int ret = 0;vector<int> container(n, 0);//记录每一个bar左边最大高度for(int i = 0; i < n; i++){container[i] = maxheight;maxheight = max(maxheight, A[i]);}maxheight = 0;//记录每一个bar右边最大高度，并找到瓶颈，统计存水量for(int i = n – 1; i >= 0; i–){container[i] = min(maxheight, container[i]);maxheight = max(maxheight, A[i]);ret += container[i] – A[i] > 0 ? container[i] – A[i] : 0;}return ret;}};</span>

这个方法是一种常见技巧，从两边各扫描一次得到我们需要维护的变量，通常适用于当前元素需要两边元素来决定的问题，类似的题目还有candy.

Answer 2: 优化算法

思路：我们还是使用两个指针a和b, 每一次循环，我们更新左边最大的高度从A[0,1,…a]，和右侧最大的高度从A[b, b+1, …n-1]，如果（leftmax < rightmax），那么至少leftmax – A[a]的水量可以被存进总量，而不用考虑【a,b】之间的情况，因为我们知道在右侧有一个更高的屏障（rightmax > leftmax）。同时，，我们也知道，只能在a处只能存储最多leftmax – A[a]的水量，因为leftmax是左边最大的高度。所以，我们得到这样的结论，在坐标a处，我们恰能存储的水量就是leftmax – A[a]. 我们可以用同样的逻辑应用到当leftmax > rightmax。每一次循环，我们都对应的移动a或者b. 最后两者相遇时，循环结束。优化的算法，我们只需要一次扫描即可。

复杂度：O(N), 空间复杂度O(1)

AC Code:

class Solution {public:int trap(int A[], int n) {int sum = 0;int a = 0;int b = n – 1;int leftmax = 0;int rightmax = 0;while(a <= b){leftmax = max(leftmax, A[a]);rightmax = max(rightmax, A[b]);if(leftmax < rightmax){sum += leftmax – A[a];a++;}else{sum += rightmax – A[b];b–;}}return sum;}};优化的方法，代码更加简洁，不过理解起来稍微有点难，需要对问题理解很清晰，不仅使用了动态规划，同时还利用了些贪心的思想，这个算法每个元素只被访问一次。这种两边往中间夹逼的方法也比较常用，它的核心思路就是向中间夹逼时，能确定接下来移动一侧窗口不可能使结果变得更好（不可能获得更大储水量），所以每次都能确定移动一侧指针，直到相遇为止。用到一些贪心的方法，如Two Sum, Container With Most Water.

而你自己根本不想从中跑出来。学习啦分享旅行唯美心情说说语录，仅供参考！