Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

我们需要维护一个递增的stack。

举例现在在stack里是1，3，5，7。现在来了4，说明以7为高度生成矩阵已经不可能在增长了。把7pop出来，算出以7为高的矩阵和全局比较。在继续这么比较。在数组最后push -1进去，使stack里剩余的高度都能被计算。实际在stack里是高度对应的Index，不是高度本身。宽度：当stack已经为空了则为当前要push的i，否则为i - stack.peek() - 1。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= height.length; i++) {
            int h = i != height.length ? height[i] : -1;
            while (!stack.isEmpty() && height[stack.peek()] > h) {
                int index = stack.pop();
                int w = stack.isEmpty() ? i : (i - stack.peek() - 1);
                max = Math.max(max, height[index] * w);
            }
            stack.push(i);
        }
        return max;
    }
}