单调栈及其应用

单调栈

单调栈就是栈里面存放的数据都是有序的，所以可以分为单调递增栈和单调递减栈两种。
1.单调递增栈就是从栈底到栈顶是从大到小
2.单调递减栈就是从栈底到栈顶是从小到大
接下来通过例题进行介绍：博文学习来源

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

给出一个矩形统计图，它的每个矩形的宽度都为1，高度是题目所给。要你求出这个矩形图中最大面积的长方形。
矩形统计图的数据为 [4, 3, 2, 5, 6]

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

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

代码实现

import java.util.Stack;
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;
    }
}

变形（拓展到二维）

【题目】
给定一个整型矩阵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.

解析
若矩阵大小为O（MN），则时间复杂度为O（MN）的解法为：
1.对矩阵的每一行进行切割，统计以当前行为底的情况下，每个位置往上1的数量。
(若当前位置为1，则统计从当前位置开始向上连续1的数量；若当前位置为0，则数量计为0）
例如map=
1 0 1 1
1 1 1 1
1 1 1 0
第1行height={1，0，1，1}
第2行height={2，1，2，2}
第3行height={3，2，3，0}
2.计算每一行为底的情况下，最大的矩形是什么。
以height={3，2，3，0}为例

代码实现：

import java.util.Stack;
public class MaximalRectangle {
    /**
     * 给定一个数组[4,3,2,5,6]，每一个数代表一个矩形的高度，组成的一个二维数组，求其中的最大矩形
     * 解法，用最大单调栈的结构来求解，用来求解一个连续的无规则面积中最大的矩形面积
     */
    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;
    }
}