Largest Rectangle in Histogram -- LeetCode

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

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

Largest Rectangle in Histogram -- LeetCode,布布扣,bubuko.com

Largest Rectangle in Histogram -- LeetCode

原文：http://blog.csdn.net/linhuanmars/article/details/20524507