目录Problem: 42. 接雨水
思路
作为自己独立完成的第一道困难题,我觉得有必要纪念一下。就是单调栈的思路,不过需要减去栈中的每一项才是雨水的体积。最后一个因为不是柱子,所以在结束循环时可能会出现栈未空的情况,需要倒着再考虑一遍。
解题方法
遇到比当前大的就改变low,然后计算雨水含量,否则就入栈,栈未空时倒着再考虑一遍
复杂度
时间复杂度:
添加时间复杂度, 示例: \(<O(3n)\)
空间复杂度:
\(O(n)\)
Code
class Solution {
public:
int trap(vector<int>& height) {
stack<int> temp;
int n=height.size();
int low=0,fast=1,ans=0;
if(n<=1) return 0;
while (fast<n)
{
if(height[fast]<height[low]){
temp.push(height[fast]);
fast++;
}
else{
int s=temp.size();
int tempheight=s*height[low];
while (!temp.empty())
{
int a=temp.top();
temp.pop();
tempheight-=a;
}
ans+=tempheight;
low=fast;
fast++;
}
}
if(!temp.empty()){
int a=0,count=0,tempheight=0;
bool judge=false;
while (!temp.empty())
{
if(temp.top()>=a) {
ans=ans+tempheight+a*count;
count=0;
tempheight=0;
a=temp.top();
}
else {count++;tempheight-=temp.top();}
temp.pop();
if(temp.size()==0&&judge==false) {temp.push(height[low]);judge=true;}//这里因为栈前面是有高柱子的,所以要把low按进去再考虑一遍
}
}
return ans;
}
};
标签:tempheight,temp,int,复杂度,42,low,ans,leetcode,解法
From: https://www.cnblogs.com/oxidationreaction/p/17997087