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.

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.

Solution: run time complexity is O(n), space complexity is O(n).

"维护一个栈，这个栈从低向上的高度是依次递增的，如果遇到当前bar高度比栈顶元素低，那么就出栈直到满足条件，过程中检测前面满足条件的矩阵。关键问题就在于在出栈时如何确定当前出栈元素的所对应的高度的最大范围是多少。答案跟Longest Valid Parentheses中括号的范围相似，就是如果栈已经为空，说明到目前为止所有元素（当前下标元素除外）都比出栈元素高度要大（否则栈中肯定还有元素），所以矩阵面积就是高度乘以当前下标i。如果栈不为空，那么就是从当前栈顶元素的下一个到当前下标的元素之前都比出栈元素高度大（因为栈顶元素第一个比当前出栈元素小的)。"

Reference: http://blog.csdn.net/linhuanmars/article/details/20524507

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

Or:

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