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<int> peak;
int ans = ;
for(int i = ; i < n - ; i++) //找到第一个山峰
{
if(A[i] > A[i + ])
{
peak.push_back(i);
break;
}
}
if(peak.empty())
{
return ; //没有山谷 没水
}
int maxheight = A[peak[]];
for(int i = peak[] + ; i < n; i++) //找剩下的山峰
{
if(A[i] > A[i - ]) //比上一个值大 新山峰
{
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 = ; i < peak.size() - ; i++) //获得水量 依次向两个山峰间加水
{
int height = min(A[peak[i]], A[peak[i+]]); //水平面是两个山峰中矮一点的那个
for(int j = peak[i] + ; j < peak[i+]; j++)
{
ans += max(height - A[j], ); //防止5 4 1 2 这种水平面比中间非山峰处低的情况
}
}
return ans;
}
};
大神的思路：没有像我一样先找所有的山峰，而是边遍历边获得每个坐标位置的水量。 而且大神是左右两边收缩的。
class Solution {
public:
int trap(int A[], int n) {
int left=; int right=n-;
int res=;
int maxleft=, maxright=;
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;
}
};