84.柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

1 动态规划+双指针解法

找到并记录左边第一个小于该数值的下标，右边第一个小于该数值的下标。
注意：初始化是有原因的，正好保证计算maxRightIndex[i] – minLeftIndex[i] – 1 的时候不存在任何的特殊情况，都能一致对待。

class Solution {
    public int largestRectangleArea(int[] heights) {
        //双指针+动态规划，记录左边第一个小于该数值的下标，右边第一个小于该数值的下标
        int len = heights.length;
        int[] minLeftIndex = new int[len];
        int[] maxRightIndex = new int[len];
        minLeftIndex[0] = -1;//为什么这样初始化呢？
        for(int i = 1; i < len; i ++){
            int t = i - 1;
            while(t >= 0 && heights[t] >= heights[i]){
                t = minLeftIndex[t];
            }
            minLeftIndex[i] = t;
        }
        maxRightIndex[len - 1] = len;
        for(int i = len - 2; i >= 0; i --){
            int t = i + 1;
            while(t < len && heights[t] >= heights[i]){
                t = maxRightIndex[t];
            }
            maxRightIndex[i] = t;
        }
        int res = 0;
        for(int i = 0; i < len; i ++){
            int w = maxRightIndex[i] - minLeftIndex[i] - 1;
            int h = heights[i];
            res = Math.max(res, w * h);
        }
        return res;
    }
}

2 单调栈

一开始忘记了第三种情况的push语句。
还有思考数组长度。

class Solution {
    public int largestRectangleArea(int[] heights) {
        //保证栈的递增顺序，找到左侧和右侧不小于mid的下标。
        int len = heights.length;
        int[] newHeights = new int[len + 2];
        for(int i = 1; i <= len; i ++){
            newHeights[i] = heights[i - 1];
        }
        heights = newHeights;
        int res = heights[1];
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1; i <= len + 1; i ++){
            if(heights[i] > heights[stack.peek()]){
                stack.push(i);
            }else if(heights[i] == heights[stack.peek()]){
                stack.pop();
                stack.push(i);
            }else{
                while(heights[i] < heights[stack.peek()]){
                    int mid = stack.pop();
                    int left = stack.peek();
                
                    int w = i - left - 1;
                    int h = heights[mid];
                    //System.out.println(left);
                    //System.out.println(i);
                    //System.out.println(h);
                    //System.out.println("");
                    res = Math.max(res, h * w);
                }
                stack.push(i);
            }
        }
        return res;
    }
}