leetcode-42. 接雨水之单调栈
程序员文章站
2024-01-20 12:31:28
...
题目
前天学习了一道单调栈的问题(拼接最大数),又找到一道类似方法的题目,而且也是hard难度的,说明这个单调栈是算法中比较难的点
方法一
想了很久u最后搞出一种时间复杂度为O(n2)的方法,是先找到数组中的最大值max,然后从1到max向上遍历,找出大于等于1,2,3…max的所有数,求他们的距离之和就是每一层可以装下的雨水!
class Solution {
public:
int trap(vector<int>& height) {
if(height.size() == 0)
return 0;
auto iter = max_element(height.begin(),height.end());
int max_num = *iter;
int sum = 0;
for(int i=1;i<=max_num;i++){
int pos = 0;
int count = 0;
for(int j=0;j<height.size();j++){
if(height[j]>=i){
if(count == 0)
pos = j;
else{
sum += (j-pos-1);
pos = j;
}
count++;
}
}
}
return sum;
}
};
很显然对于这种hard的题目这个方法是不可能不超时的~
方法二
一句话:找左右两边最大值中小者,减去本身高度,就是每个数对于的雨水量!
class Solution {
public:
int trap(vector<int>& height) {
if(height.size() == 0)
return 0;
vector<int> left(height.size(),0);
// left数组是用于记录每个数左边的最大值
vector<int> right(height.size(),0);
// right数组是用于记录每个数右边的最大值
left[0] = height[0];
right[height.size()-1] = height[height.size()-1];
for(int i=1;i<height.size();i++)
left[i] = max(left[i-1],height[i]);
for(int i=height.size()-2;i>=0;i--)
right[i] = max(right[i+1],height[i]);
int sum = 0;
for(int i=0;i<height.size();i++){
int tmp = min(left[i],right[i]);
tmp = max(0,tmp - height[i]);
sum += tmp;
}
return sum;
}
};
方法三
单调栈方法,维护递减的单调栈,但是这里用单调栈其实相对于方法二来说还是复杂了;
这里直接引用官方题解的解释:
“
我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到ans 。
“
链接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
class Solution {
public:
int trap(vector<int>& height) {
stack<int> s;
// 栈用于压入数的索引,方便计算距离
int sum = 0;
for(int i=0;i<height.size();i++){
int water = 0;
while(!s.empty() && height[s.top()]<height[i]){
int top = height[s.top()];
s.pop();
if(s.empty())
break;
int distance = i - s.top() - 1;
int high = min(height[s.top()],height[i]) - top;
water = water + distance*high;
}
s.push(i);
sum += water;
}
return sum;
}
};