一、84. 柱状图中最大的矩形

1、思路

单调递增，遇到低的矩形时，单调性破坏后，需要将栈里面的数据逐个出栈，宽度累加，然后计算面积,取最大值

2、代码

;
class Solution {

    public int largestRectangleArea(int[] heights) {
        // 单调递增，当单调性破坏后，需要将栈里面的数据逐个出栈，然后计算面积,取最大值
        // 2 入栈
        // 2 比 1 大，破坏单调递增，计算结果，出栈,栈空

        // 1入栈 5 入栈 6 入栈
        // 6比 2 大，破坏单调递增.计算结果出栈，结果比较大小,取大, 6出栈，宽度+1 , 5一样，依次出栈，宽度累加，取最大值,宽度+1
        // 1 比2 小 2入栈 ，同理，2 比 3小 ,3 入栈

        // 最后如果栈不为空,则计算栈里面面积最大数据

        Stack<Rect> stack = new Stack();
        int maxResult = 0;
        for (int h : heights) {
            int widthSum = 0;
            // 栈不为空并且栈顶（之前）高度大于等于当前高度，则计算栈里面面积最大数据
            while (!stack.empty() && stack.peek().getHeight() >= h) {
                Rect r = stack.pop();
                int a = r.getHeight(); // 栈顶高度
                widthSum += r.getWidth(); // 栈顶宽度 累加
                maxResult = Math.max(a * widthSum, maxResult);

            }
            Rect rect = new Rect(widthSum + 1, h);
            stack.push(rect);
        }
        int widthSum = 0;
        // 栈不为空，则计算栈里面面积最大数据
        while (!stack.empty()) {
            Rect r = stack.pop();
            int a = r.getHeight(); // 栈顶高度
            widthSum += r.getWidth(); // 栈顶宽度 累加
            maxResult = Math.max(a * widthSum, maxResult);

        }
        return maxResult;
    }
}

class Rect {
    int width;
    int height;

    public Rect() {

    }

    public Rect(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public int getWidth() {
        return width;
    }

    public int getHeight() {
        return height;
    }
}

二、42. 接雨水

1、思路

单调递减，遇到高的停止, 单调性破坏后，需要将栈里面的数据逐个出栈，宽度累加，然后计算面积,面积累加，注意边界，水流出

2、代码

class Solution {
    public int trap(int[] height) {
        // 单调递减，遇到高的停止,计算栈里面面积,累加宽度，出栈
        //2 1 0 1
        int maxResult = 0;
        Stack<Rect> stack = new Stack();
        for (int h : height) {
            int widthSum = 0;
            while (!stack.empty() && stack.peek().getHeight() < h) {
                Rect r = stack.pop();
                int width = r.getWidth();
                int h2 = r.getHeight();

                // 计算面积,宽度累加
                widthSum += width;
                // 如果弹一个后，栈为空，则水从左边流走了
                if(stack.empty()){
                    continue;
                }
               maxResult += widthSum*(Math.min(h,stack.peek().getHeight()) - h2);
            }
            Rect rect = new Rect(widthSum + 1, h);
            stack.push(rect);
        }

        return maxResult;
    }

}

class Rect {
    int width;
    int height;

    public Rect() {

    }

    public Rect(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public int getWidth() {
        return width;
    }

    public int getHeight() {
        return height;
    }
}

三、总结

单调栈题目思维模板：

• 确定递增递减 --------关键在于考虑 前面不能影响后面 条件
• 柱状图中最大的矩形题目中若 h[i-1] > h[i] ，则h[i-1] 这个高度就无法影响到更后面，自然可以单独计算

单调栈题目代码模板：

• for循环遍历每个元素
• ​ while（栈顶与新元素不满足单调性）{弹栈 ，更新答案，累加宽度}
• ​ 入栈