【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）！