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.
从两端向中间夹逼，比两端较矮那根还矮的部分就可以用水补齐了。
class Solution {
public:
int trap(int A[], int n) {
if(n <= 2) return 0;
int areas = 0;
int start = 0;
int end = n - 1;
while(start <= end){//向左端看齐
if(A[start] <= A[end]){
int i = start + 1;
while(i < end && A[i] < A[start])
areas += A[start] - A[i++];
start = i;
}
else{//向右端看齐
int j = end - 1;
while(j > start && A[j] < A[end])
areas += A[end] - A[j--];
end = j;
}
}
return areas;
}
};