Trapping Rain Water(Medium)
题目描述
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.
题目链接
解题思路
先假设黑色部分不占空间，按y轴方向计算出总的体积。最后减去黑色部分占的体积。
时间复杂度：O（n）
空间复杂度：O（1）
参考代码
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
// write your code here
int n = heights.size();
int l = 0, r = n - 1;
int ans = 0, maxH = 0, preH = 0;
while (l < r) {
int h = min(heights[l], heights[r]);
ans += (h - preH) * (r - l + 1);
while (l < r && heights[l] <= h) ++ l;
while (l < r && heights[r] <= h) -- r;
maxH = max(maxH, h);
preH = h;
}
for (int i = 0; i < n; ++ i) {
ans -= min(heights[i], maxH);
}
return ans;
}
};