给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
> 双指针法
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
if(len <= 2) return 0;
int sum = 0;
vector<int> leftmax(len,0);
vector<int> rightmax(len,0);
leftmax[0] = height[0];
rightmax[len-1] = height[len-1];
for(int i = 1;i < len;i++){
leftmax[i] = max(leftmax[i-1],height[i]);
}
for(int i = len-2;i >= 0;i--){
rightmax[i] = max(rightmax[i+1],height[i]);
}
for(int i = 1;i < len-1;i++){
int count = min(leftmax[i],rightmax[i]) - height[i];
if(count > 0) sum += count;
}
return sum;
}
};
> 单调栈
class Solution {
public:
int trap(vector<int>& height) {
//其实就是寻找下一个更高地势
int len = height.size();
if(len == 1) return 0;
int sum = 0;
stack<int> sta;
sta.push(0);
for(int i = 1;i < len;i++){
int mid = sta.top();
while(height[mid] <= height[i]){
//出栈
sta.pop();
if(!sta.empty()){
int h = min(height[i],height[sta.top()]) - height[mid];
int w = i - sta.top() - 1;
sum += h*w;
mid = sta.top();
}
else{
break;
}
}
//入栈
sta.push(i);
}
return sum;
}
};
标签:leftmax,rightmax,int,42,len,height,雨水
From: https://www.cnblogs.com/lihaoxiang/p/17477511.html