Largest Rectangle in Histogram(Hard)直方图最大面试

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.

解题思路1：Stack

解决这个问题的关键是用栈保存直方图的索引，栈内存储的是高度递增的下标。

对于每一个直方图高度，分两种情况。

1. 当栈空或者当前高度大于等于栈顶下标所指示的高度时，当前下标入栈。
2. 否则，当前栈顶出栈，并且用这个下标所指示的高度计算面积。关键问题就在于在出栈时如何确定当前出栈元素的所对应的高度的最大范围是多少。答案跟Longest Valid Parentheses 中括号的范围相似， 就是如果栈已经为空， 说明到目前为止所有元素（当前下标元素除外）都比出栈元素高度要大（否则栈中肯定还有元素），所以矩阵面积就是高度乘以当前下标i。如果栈不为空，那么就是从当前栈顶元素的下一个到当前下标元素的前一个都比出栈元素高度大（因为栈顶元素的高度比当前出栈元素小）。

public int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }

    LinkedList<Integer>  stack = new LinkedList<>();
    int max = height[0];
    int i = 0;

    while(i < height.length) {
        if(stack.isEmpty() || (height[i] >= height[stack.peek()])) {
            stack.push(i);
            i++;
        } else {
            int hei = height[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(max,hei*width);
        }
    }

    while (!stack.isEmpty()) {
        int hei = height[stack.pop()];
        int width = stack.isEmpty() ? i : i - stack.peek() - 1;
        max = Math.max(hei * width, max);
    }

    return max;
}

References:

1 SegmentFault解法

2 Maximal Rectangle

3 Longest Valid Parentheses