单调栈

介绍：单调栈是一种按照元素单调递增或递减的顺序排列的数据结构。

相关题目

序号	题目	难度
1	84. 柱状图中最大的矩形	hard
2	单元格

1. 柱状图中最大的矩形

image.png

第一种：暴力解法：

第二种：单调栈：

    public int largestRectangleArea(int[] heights) {
        if (heights == null) {
            return 0;
        }
        
        int size = heights.length;
        int[] input = new int[size + 2];
        input[0] = 0;
        input[size + 1] = 0;
        
        // 记得初始化
        for(int index = 1; index < size + 1; index++) {
            input[index] = heights[index - 1];
        }
        
        int[] result = new int[size + 2];
        
        Stack<Integer> stack = new Stack<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < size + 2; i++) {
            // 重点：如果新的元素比栈顶top元素小，则需说明当前递增的规律被打破了，为了使新的元素入栈，需要将破坏规矩的元素出栈，并计算结果
            while(!stack.isEmpty() && (input[stack.peek()] > input[i])) {
                int top = stack.pop();
                int left = stack.peek();
                result[top] = (i - left - 1) * input[top];
                max = Math.max(result[top], max);
            }
            // 入栈的是索引，而不是元素内容
            stack.push(i);
        }
        return max;
    }