[LintCode] Trapping Rain Water

时间:2024-08-05 23:35:20

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.

[LintCode] Trapping Rain Water

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;
}
};