单调栈及其应用

单调栈

博主是因为在刷LeetCode题的时候才知道有单调栈这个数据结构，说起来也是真的巧妙。一开始是在LeetCode739题（每日温度）接触到的，其实单调栈就是从数组中找到左右两边比你大的数或者比你小的数而且时间复杂度为O(N)。以下讲一些单调栈的特性和一些应用题

什么是单调栈

单调栈就是栈里面存放的数据都是有序的，所以可以分为单调递增栈和单调递减栈两种。

单调递增栈就是从栈底到栈顶是从大到小
单调递减栈就是从栈底到栈顶是从小到大

单调栈的经典题目（求最大子矩阵的大小）

【题目】
给定一个整型矩阵map，其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量。
例如：
1 1 1 0
其中，最大的矩形区域有3个1，所以返回3。
再如：
1 0 1 1
1 1 1 1
1 1 1 0
其中，最大的矩形区域有6个1，所以返回6.

要想解答这道题，我先引入另一道题来更好得帮你理解。

给出一个矩形统计图，它的每个矩形的宽度都为1，高度是题目所给。要你求出这个矩形图中最大面积的长方形。

1	矩形统计图的数据为 [4, 3, 2, 5, 6]

思路：

准备一个栈，栈低到栈顶是从小到大的。栈如图所示

第一个下标是0，值是4，栈为空，放入栈中。
第二个下标为1，值为3，比栈顶（此时是4）小，不符合栈低到栈顶从小到大，所以弹出栈顶（4），此时4最左边界就是-1，最右就是1，所以弹出的面积就是4 *（1-（-1）-1）为4；然后3入栈
第三个下标为2，值为2，比栈顶（此时是3）小，不符合栈低到栈顶从小到大，所以弹出栈顶（3），此时3的最左边界是-1，最右就是2，所以弹出的面积是3 *（2-（-1）-1）为6；然后2入栈
第四个下标为3，值为5，比栈顶（此时是2）大，符合栈低到栈顶从小到大，所以5入栈
第五个下标为4，值为6，比栈顶（此时是6）大，符合栈低到栈顶从小到大，所以6入栈
此时没有值可以入栈了，弹出6，此时6的最左边界就是栈顶（5）的下标3，最右边界就是5，所以弹出的面积是6 *（5-（3）-1）为6
继续出栈，面积为5 *（5-（2）-1）为10；
继续出栈，面积为2 *（5-（-1）-1）为10；
最大值就是10，所以输入10

ps：建议画图，然后按照我上面写的步骤尝试一遍，你就很清楚整个过程了。

代码：

 import java.util.Stack;

/**
 * @author god-jiang
 * @date 2020/1/8
 */
public class MaximalRectangle {
    /**
     * 给定一个数组[4,3,2,5,6]，每一个数代表一个矩形的高度，组成的一个二维数组，求其中的最大矩形
     * 解法，用最大单调栈的结构来求解，用来求解一个连续的无规则面积中最大的矩形面积
     *
     * @return
     */
    public static int maxRecFromBottom(int[] height) {
        int maxArea = 0;
        if (height.length <= 0)
            return 0;
        //从小到大的单调栈
        Stack<Integer> stack = new Stack<>();
        //这一步是在求每次遇到不是单调递增的时候那个柱子的面积
        for (int i = 0; i < height.length; i++) {
            //如果栈不为空，且当前元素小于栈顶元素
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                int j = stack.pop();
                //左边界
                int k = stack.isEmpty() ? -1 : stack.peek();
                //(右边界 - 左边界)*高度
                int curArea = (i - k - 1) * height[j];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }
        //求整个单调递增的面积
        while (!stack.isEmpty()) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            //当前的右边界就是数组长度
            int curArea = (height.length - k - 1) * height[j];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;

    }
}

回归正题，来解答一开始的那道题

思路就是当传入一个二维数组的时候，我们把它压缩成一个一维数组的形式进行解答。
从第0行开始调用我们上面那个求矩形的面积的函数，求完求第0行到第一行，依次类推，反正当前要是有0的话就是0，不是0就加1.

代码

import java.util.Stack;

/**
 * @author god-jiang
 * @date 2020/1/8
 */
public class MaximalRectangle {
    /**
     * 给定一个数组[4,3,2,5,6]，每一个数代表一个矩形的高度，组成的一个二维数组，求其中的最大矩形
     * 解法，用最大单调栈的结构来求解，用来求解一个连续的无规则面积中最大的矩形面积
     *
     * @return
     */
    public static int maxRecFromBottom(int[] height) {
        int maxArea = 0;
        if (height.length <= 0)
            return 0;
        //从小到大的单调栈
        Stack<Integer> stack = new Stack<>();
        //这一步是在求每次遇到不是单调递增的时候那个柱子的面积
        for (int i = 0; i < height.length; i++) {
            //如果栈不为空，且当前元素小于栈顶元素
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                int j = stack.pop();
                //左边界
                int k = stack.isEmpty() ? -1 : stack.peek();
                //(右边界 - 左边界)*高度
                int curArea = (i - k - 1) * height[j];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }
        //求整个单调递增的面积
        while (!stack.isEmpty()) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            //当前的右边界就是数组长度
            int curArea = (height.length - k - 1) * height[j];
            maxArea = Math.max(maxArea, curArea);
        }
        return maxArea;
    }

    public static int maxRecSize(int[][] map) {
        int maxArea = 0;
        if (map.length <= 0)
            return 0;
        int[] height = new int[map[0].length];
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                //如果当前行不是0，则累加高度
                if (map[i][j] != 0)
                    height[j] += map[i][j];
                else//如果当前行的值为0，则高度为0
                    height[j] = 0;
            }
            //求出每一行的最大矩形面积
            maxArea = Math.max(maxRecFromBottom(height), maxArea);
        }

        return maxArea;
    }
}

总结

以上就是我接触到的单调栈，当然有许多的应用，但是也不可能一一列举，只是抽出比较经典的题目来讲一下，然后就是觉得写得还不错的给博主点点赞和关注一波，谢谢大家的支持了。