https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

单调栈

以3为高，左右扩，只能是它自己面积是3.

下一个数， 1位置的2， 我只要求出左边离我最近的比我小的数在哪，右边离我最近的比我小的数在哪，我就知道我能扩几个刻度了，所以， 以2个格子为高度的面积是4

把每个数作高都枚举一遍，最大的矩形就是答案，

你可以搞一个单调栈，然后把每个位置的2个信息，全都生成好，然后去结算， 整体O(N)
但是这道题有常数级别的优化，

那如果有相等的呢？也一样，看这个例子

1 —-> 4弹出之后，真正精彩的来了， 面对相等，我们怎么办？也弹出

虽然此刻 0—-> 3知道左边的最近的比他小的，但是不知道右边最近的比他小的， 怎么办？依然求个答案
我就认为2位置的3是我扩不到的答案， 所以面积是3 x 2 = 6， 这不是个准确的答案哦
然后把2位置的3进栈

有朝一日2位置的3可能能求出最优解， 对于重复值，我们每一步可能求得不是准确解，但是不要紧，最后一个不会错过整体最优解，

这里精彩得地方在于 相等值我也让它弹出， 因为会有后人帮我复仇，也就是等到后人出栈得时候，会为我讨个说法得，所以我现在算得不准确也没关系， 最好得答案最后肯定会抓住，
其实这种思想就是 舍弃部分可能性，但是不影响我最终的答案

（你也可以完全按照单调栈来实现）

正统得单调栈解法是这样得

// 正统单调栈解法
    public int largestRectangleArea(int[] heights) {
        int[][] ans = getNearLess(heights);
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            if (ans[i][1] == -1) {
                maxArea = Math.max(maxArea,  (heights.length - ans[i][0]  - 1 )* heights[i]) ;
            } else {
                maxArea = Math.max(maxArea, (ans[i][1] - ans[i][0] - 1) * heights[i]) ;
            }
        }
        return maxArea;
    }
    public int[][] getNearLess(int[] nums) {
        int res[][] = new int[nums.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]) {
                List<Integer> popIs = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                for (Integer popI : popIs) {
                    res[popI][0] = leftLessIndex;
                    res[popI][1] = i;
                }
            }
            if (!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]) {
                stack.peek().add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while (!stack.isEmpty()) {
            List<Integer> popIs = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            for (Integer popI : popIs) {
                res[popI][0] = leftLessIndex;
                res[popI][1] = -1;
            }
        }
        return res;
    }

但是此题我们可以让它相等得时候也弹出

public static int largestRectangleArea2(int[] height) {
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
            int k = stack.pop();
            int leftIndexLess = stack.isEmpty() ? -1 : stack.peek();
            maxArea = Math.max( maxArea, (i - leftIndexLess - 1) * height[k]);
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int k = stack.pop();
        int leftIndexLess = stack.isEmpty() ? -1 : stack.peek();
        maxArea = Math.max( maxArea, (height.length - leftIndexLess - 1) * height[k]);
    }
    return maxArea;
}