Largest Rectangle in Histogram leetcode

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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

维护一个栈, 这个栈从低向上的高度是依次递增的，如果遇到当前bar高度比栈顶元素低，那么就出栈直到满足条件，过程中检测前面满足条件的矩阵。

1.当栈空或者当前高度大于栈顶下标所指示的高度时，当前下标入栈。否则，2：当前栈顶出栈，并且用这个下标所指示的高度计算面积。然后大于当前高度的栈顶依次出栈并计算高度.如果栈已经为空，说明到目前为止所有元素（当前下标元素除外）都比出栈元素高度要大（否则栈中肯定还有元素），所以矩阵面积就是高度乘以当前下标i。如果栈不为空，那么就是从当前栈顶元素的下一个到当前下标的元素之前都比出栈元素高度大（因为栈顶元素第一个比当前出栈元素小的）
3. fake一个最后一个直方高度为0 (这样面积也为0)
4. 因为每次入栈计算的面积都是出栈元素的面积 所以最后添加一个高度为0的元素让所有的元素都出栈计算面积

首先，如果栈是空的，那么索引i入栈。那么第一个i=0就进去吧。注意栈内保存的是索引，不是高度。然后i++。

然后继续，当i=1的时候，发现h[i]小于了栈内的元素，于是出栈。（由此可以想到，哦，看来stack里面只存放单调递增的索引）

这时候stack为空，所以面积的计算是h[t] * i.t是刚刚弹出的stack顶元素。也就是蓝色部分的面积。

继续。这时候stack为空了，继续入栈。注意到只要是连续递增的序列，我们都要keep pushing，直到我们遇到了i=4，h[i]=2小于了栈顶的元素。

这时候开始计算矩形面积。首先弹出栈顶元素，t=3。即下图绿色部分。

接下来注意到栈顶的（索引指向的）元素还是大于当前i指向的元素，于是出栈，并继续计算面积，桃红色部分。

最后，栈顶的（索引指向的）元素大于了当前i指向的元素，循环继续，入栈并推动i前进。直到我们再次遇到下降的元素，也就是我们最后人为添加的dummy元素0.

同理，我们计算栈内的面积。由于当前i是最小元素，所以所有的栈内元素都要被弹出并参与面积计算。

注意我们在计算面积的时候已经更新过了maxArea。

总结下，我们可以看到，stack中总是保持递增的元素的索引，然后当遇到较小的元素后，依次出栈并计算栈中bar能围成的面积，直到栈中元素小于当前元素。

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int[] tem = Arrays.copyOf(height, height.length + 1);
        int max = 0;
        int i = 0;
        while (i < tem.length) {
            if (stack.isEmpty() || tem[i] >= tem[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int t = stack.pop();
                if (!stack.isEmpty()) {
                    max = Math.max(max, tem[t] * (i - stack.peek() - 1));
                } else {
                    max = Math.max(max, tem[t] * i);
                }
            }
        }
        return max;
    }
}

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i <= height.length; i++) {
            int h;
            if (i == height.length) {
                h = 0;
            } else {
                h = height[i];
            }
            if (stack.isEmpty() || h >= height[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && h < height[stack.peek()]) {
                    int k = stack.pop();
                    if (stack.isEmpty()) {
                        max = Math.max(i * height[k], max);
                    } else {
                        max = Math.max(max, (i - stack.peek() - 1)*height[k]);
                    }
                }
                stack.push(i);
            }
        }
        return max;
    }
}