Largest Rectangle in Histogram 122

Question

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.

Example

Given height = [2,1,5,6,2,3],

return 10.

Solution

用stack存储高度的index,当当前高度大于栈顶高度时,直接将当前高度入栈;当前高度小于等于栈顶高度时,将栈顶元素出栈,再次判断直到栈中没有比当前高度大的元素,再将当前高度入栈。这样,栈中每个元素出栈时,其左边的元素为该元素在数组中左边第一个小于该元素的元素,而导致该元素出栈的元素(即此轮的当前高度)为该元素在数组中右边第一个小于该元素的元素,因此用右边界减去左边界再减1为满足该元素高度的最大宽度,再乘以该高度为该元素高度的最大面积。特殊情况为该出栈元素左边没有元素,表示从数组的第一个元素到该元素之间的元素都比该元素高度大,所以该元素的最大宽度为从数组开头到其右边界。当数组所有元素都遍历过之后,若stack中还有元素剩下,则将当前元素高度赋值为-1,这样stack中所有元素都会出栈。

代码如下:

public class Solution {
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        // write your code here

        if(height == null || height.length == 0){
            return 0;
        }

        Stack<Integer> stack = new Stack<Integer>();

        int max = -1;
        for(int i = 0; i <= height.length; i++){
            int current = (i == height.length) ? -1 : height[i];
            while(!stack.isEmpty() && current <= height[stack.peek()]){
                int h = height[stack.pop()];
                int w = (stack.isEmpty()) ? i : i - stack.peek() - 1;
                max = Math.max(max, w * h);
            }
            stack.push(i);
        }

        return max;
    }
}

results matching ""

    No results matching ""