Given n non-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], return 6.

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. 

 

思路：

我自己的想法，先遍历一遍数组找到所有的山峰位置，在例子中是1,3,7,10，然后再填充两个山峰之间的水，获得水量

class Solution {public:    int trap(int A[], int n) {        bool haswater = false;        vector
     
       peak;        int ans = 0;        for(int i = 0; i < n - 1; i++) //找到第一个山峰        {            if(A[i] > A[i + 1])            {                peak.push_back(i);                break;            }        }        if(peak.empty())        {            return 0; //没有山谷 没水        }        int maxheight = A[peak[0]];        for(int i = peak[0] + 1; i < n; i++) //找剩下的山峰        {            if(A[i] > A[i - 1]) //比上一个值大 新山峰            {                while(A[i] > A[peak.back()] && A[peak.back()] < maxheight) //比之前的山峰高，且之前的山峰不是最高峰，删掉之前的 第一个山峰不能删                {                    peak.pop_back();                }                maxheight = (A[i] > maxheight) ? A[i] : maxheight; //新的最高峰                peak.push_back(i);             }        }        for(int i = 0; i < peak.size() - 1; i++) //获得水量 依次向两个山峰间加水        {            int height = min(A[peak[i]], A[peak[i+1]]); //水平面是两个山峰中矮一点的那个            for(int j = peak[i] + 1; j < peak[i+1]; j++)            {                ans += max(height - A[j], 0); //防止5 4 1 2 这种水平面比中间非山峰处低的情况            }        }        return ans;    }};
     

 

大神的思路：没有像我一样先找所有的山峰，而是边遍历边获得每个坐标位置的水量。 而且大神是左右两边收缩的。

class Solution {public:    int trap(int A[], int n) {        int left=0; int right=n-1;        int res=0;        int maxleft=0, maxright=0;        while(left<=right){ //没有遍历结束            if(A[left]<=A[right]){ //如果右边比较高 则处理左边                if(A[left]>=maxleft) maxleft=A[left]; //如果当前的值比左边最大值还大，那更新最大值 这个位置不会有水                else res+=maxleft-A[left]; //如果比左边最大值小那当前值一定在山谷 左边比左边最大值小 右边比右值小                left++;             }            else{                if(A[right]>=maxright) maxright= A[right];                else res+=maxright-A[right];                right--;            }        }        return res;    }};