单调栈问题

单调栈分为单调递增栈和单调递减栈

  1. 单调递增栈即栈内元素保持单调递增的栈
  2. 同理单调递减栈即栈内元素保持单调递减的栈

操作规则（下面都以单调递增栈为例）

  1. 如果新的元素比栈顶元素大，就入栈
  2. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

加入这样一个规则之后，会有什么效果

  1. 栈内的元素是递增的
  2. 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素
  3. 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

代码模板：

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}

图片.png

序号 题目 题解
1 42. 接雨水（困难） 暴力解法、优化、双指针、单调栈
2 739. 每日温度（中等） 暴力解法 + 单调栈
3 496. 下一个更大元素 I（简单） 暴力解法、单调栈
4 316. 去除重复字母（困难） 栈 + 哨兵技巧（Java、C++、Python）
5 901. 股票价格跨度（中等） 「力扣」第 901 题：股票价格跨度（单调栈）
6 402. 移掉K位数字
7 581. 最短无序连续子数组

例题：

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

img

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

核心原理：

核心原理就是针对每一个柱子求左右边界的过程，遍历到最大的面积就是此面积

求每条柱子可以向左右延伸的长度->矩形最大宽度;矩形的高->柱子的高度 计算以每一根柱子高度为高的矩形面积,维护面积最大值

朴素解：

遍历每一根柱子的高度然后向两边进行扩散找到最大宽度，复杂度 O(N2)

单调栈：

因为最终的目的是寻找对应柱子height[i]右边首个严格小于height[i]的柱子height[r]左边同理找到首个严格小于height[i]的柱子height[l]

维护一个单调递增栈(栈底->栈顶),那么每当遇到新加入的元素，如果改新的元素小于栈顶便可以确定栈顶柱子右边界，而栈顶柱子左边界就是栈顶柱下面的柱子（如果没有就是其本身）左右边界确定以后就可以进行面积计算与维护最大面积

第二点，我们栈中存的应该是高度呢还是 数组 位置，当然是位置，只有知道了位置才知道一切。。

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 单调栈
        if (heights.length==1) return heights[0];
        Deque<Integer> stack = new ArrayDeque<>();
        // 单调栈有一个小技巧
        // 在height数组前后加0 可以使得最终所有数据全部弹出
        int[] newheights = new int[heights.length+2];
        System.arraycopy(heights,0,newheights,1,heights.length);
        // Arrays.copyOf() 只能复制到新数组的头部
        int res=0;
        for(int i=0;i<newheights.length;i++){
            // 新添加的元素 为 heights[i]
            // 当 栈为空 或者 栈中元素不再满足单调时 弹栈
            while(!stack.isEmpty() && newheights[stack.peek()]> newheights[i]){
                int cur=stack.pop();
                // 计算 以当前柱子 为最高高度时，的面积
                int l=stack.peek();
                int r=i;
                res=Math.max(res,(r-l-1)*newheights[cur]);

            }
            stack.push(i);
        }
        return res;
    }
}

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

img

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m= matrix.length;
        int n= matrix[0].length;
        int res = 0;
        int max_layer = 0;
        int[] heights = new int[n];
        for(int i=0;i<m;i++){
            // 每一行 都有新栈
            int area=0;
            for(int j=0;j<n;j++){
                heights[j]=matrix[i][j]=='1'?heights[j]+1:0;
            }
            res=Math.max(res,getMax(heights));
        }
        return res;
    }
    public static  int getMax(int[] h){
            int len = h.length;
            int[] heights = new int[h.length+2];
            System.arraycopy(h,0,heights,1,h.length);
            int area=0;
            Deque<Integer> stack = new ArrayDeque<>(); 
            for(int j=0;j<len+2;j++ ){
                // 根据heights 求 当前的最大区域面积
                // 求法同84 单调栈
                while(!stack.isEmpty() && heights[stack.peek()]>heights[j]){
                    // 获取当前列高度
                    int curheight = heights[stack.pop()];
                    // 获取 两边高度
                    int left = stack.isEmpty()? 0:stack.peek();
                    int right= j;
                    // 获取面积，比较
                    area = Math.max(area,(right-left-1)*curheight);
                }
                stack.push(j);
            }
            return area;
    }
}