Largest Rectangle in Histogram - Lintcode

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 =10unit.

Example

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

Analysis

using the brute force approach, we need to find for each item, its first smaller left and its first smaller right. As soon as we encounter such question required looking for first smaller on left / right, decreasing or increasing stack (单调栈） is the way to go. A few key points when writing the decreasing / increasing stack

for (int i = 0; i <= height.length; i++){
the equal sign is important to for the next key point

if (i == height.length){
    curr = -1;
}
this means when the end of the array is reached, pop out all the values in the stack


int w = (stack.isEmpty()) ? i : i - stack.peek() - 1;
this is find the width of the rectangle

Solution

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

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

    for (int i = 0; i <= height.length; i++){
        int curr = 0;
        if (i == height.length){
            curr = -1;
        } else {
            curr = height[i];
        }

        //encounter a value which is smaller than the stack top value
        while(!stack.isEmpty() && height[stack.peek()] > curr){
            int h = height[stack.pop()];
            int w = (stack.isEmpty()) ? i : i - stack.peek() - 1;
            area = Math.max(area, h * w);
        }

        stack.push(i);
    }

    return area;
}