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.
Example
Given [0,1,0,2,1,0,1,3,2,1,2,1]
, return 6
.
Challenge
O(n) time and O(1) memory
O(n) time and O(n) memory is also acceptable.
class Solution {
public:
int trap(vector<int>& heights) {
if(heights.size() < ) return ;
int waterNum = , left = , right = heights.size() - ,
leftH = heights[left], rightH = heights[right]; while(left < right){
if(leftH < rightH){
int t = left + ;
if(t < right){
if(heights[t] < leftH)
waterNum += leftH - heights[t];
else leftH = heights[t];
}
left = t;
}else{
int t = right - ;
if(t > left){
if(heights[t] < rightH)
waterNum += rightH - heights[t];
else rightH = heights[t];
}
right = t;
}
}
return waterNum;
}
};