【c++刷题笔记-单调栈】day49: 42. 接雨水 、84.柱状图中最大的矩形
42. 接雨水 - 力扣(LeetCode)
思路:单调栈,第一个是比栈顶大的是右边界,栈顶元素是底,出栈后下一个栈顶元素是左边界。
使用左右边界最小值与中间元素相减算出高度,右边界减左边界减1算出宽度
1.双指针
class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
int ans=0;
vector<int>left(n);
vector<int>right(n);
//左边第一个的左边最大数为0
for(int i=1;i<n;i++){
left[i]=max(left[i-1],height[i-1]);//预处理当前数左边的最大数
}
//右边第一个的右边最大数为0
for(int i=n-2;i>=0;i--){
right[i]=max(right[i+1],height[i+1]);//预处理当前数右边的最大数
}
for(int i=1;i<n-1;i++){
int t=min(left[i],right[i]);//取最小的
if(t>height[i]){//大于当前就算出可以接的雨水数量
ans+=t-height[i];
}
}
return ans;
}
};
2.单调栈
class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
int ans=0;
stack<int>st;
st.push(0);
for(int i=1;i<n;i++){
while(!st.empty()&&height[i]>height[st.top()]){
int mid=height[st.top()];//记录中间值
st.pop();
if(st.empty()){
break;
}
int h=min(height[i],height[st.top()])-mid;//算出高度
int w=i-st.top()-1;//减一算出宽度
ans+=w*h;
}
st.push(i);
}
return ans;
}
};
84. 柱状图中最大的矩形 - 力扣(LeetCode)
思路:同上,只是换成单调递减栈。以中间值为高度,右边界减左边界减1算出宽度。选最大的值
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans=0;
stack<int>st;
//添加前导0和后导0判断原数组单调递增和单调递减的情况
heights.insert(heights.begin(),0);
heights.push_back(0);
st.push(0);
//注意是增加前导0和后导0的数组大小
for(int i=1;i<heights.size();i++){
//判断当前左右比当前小的值作为边界,当前数为高度
while(heights[i]<heights[st.top()]){//单调递减
int mid=st.top();
st.pop();
int w=i-st.top()-1;
int h=heights[mid];
ans=max(ans,w*h);
}
st.push(i);
}
return ans;
}
};
总结
单调栈。在解决左边更大或右边更大的问题可以考虑单调栈方法
原文地址:https://blog.csdn.net/qq_48662659/article/details/140658230
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!