84. Largest Rectangle in Histogram

Version #3 Array
Space O(n)
Time O(n)
用两个array分别记录当前index的最左边界和最右边界
tricky的地方在于如果i - 1比i 低，left[i]就是 i- 1
如果i-1比i 高，那么可以直接跳到left[i - 1]的那个点
It is O(n) because each left[i] can be skipped only once
If it has been skipped before, means there's some bar on its right which is lower than it, so it would never be touched again. We can only have a look at the left[x] of that x lower than it

99.69 %
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int len = heights.length;
        //closest left index lower than current
        //closest right index higher than current
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = -1;
        right[len - 1] = len;
        int p = 0;
        for (int i = 1; i < len; i++) {
            p = i - 1;
            while (p >= 0 && heights[p] >= heights[i]) {
                p = left[p];
            }
            left[i] = p;
        }
        for (int j = len - 2; j >= 0; j--) {
            p = j + 1;
            while (p < len && heights[p] >= heights[j]) {
                p = right[p];
            }
            right[j] = p;
        }
        int max = 0;
        for (int k = 0; k < len; k++) {
            max = Math.max(max, heights[k] * (right[k] - left[k] - 1));
        }
        return max;
    }
}

Version #1 Stack
Time O(n)
Space O(n)
90.01 % 
class Solution {
    public int largestRectangleArea(int[] heights) {
        // Keep track of start height
        // if a lower rectangle is found, then that height ends, it should be poped up
        // up date the lower rectangle's start point as current point
        // curr[0] -> x, curr[1] -> height
        Deque<int[]> stack = new ArrayDeque<>();
        int max = 0;
        int[] prev;
        int i = 0;
        // [2,1,5,6,2,3]
        // (0, 1) (2, 5)(3, 6)
        for (i = 0; i < heights.length; i++) {
            int currHeight = heights[i];
            int x = i;
            while (!stack.isEmpty() && stack.peekFirst()[1] >= currHeight) {
                prev = stack.removeFirst();
                max = Math.max(max, prev[1] * (i - prev[0]));
                x = prev[0];
            }
            stack.addFirst(new int[]{x, currHeight});
        }
        while (!stack.isEmpty()) {
            prev = stack.removeFirst();
            max = Math.max(max, prev[1] * (i - prev[0]));
        }
        return max;
    }
}

Version #2 Stack
89.55 %
和上面方法一样但是更巧妙，用stack里面的上一个index作为左边界
class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int x = 0;
        int max = 0;
        int left = 0;
        int i = 0;
        for (i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peekFirst()] >= heights[i]) {
                x = stack.removeFirst();
                // left bound is its previous in stack
                left = stack.isEmpty() ? -1 : stack.peekFirst();
                // right bound is current index
                max = Math.max(max, heights[x] * (i - left - 1));
            }
            stack.addFirst(i);
        }
        while (!stack.isEmpty()) {
            x = stack.removeFirst();
            left = stack.isEmpty() ? -1 : stack.peekFirst();
            max = Math.max(max, heights[x] * (i - left - 1));
        }
        return max;
    }
}