Largest Rectangle in Histogram

Question

from lintcode
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Idea

For each bar, you try to extend to its left and to its right until a lower bar is encountered. Then calculated the area. However, this is just the idea. To implement this, you have to write in a very indirect way without recursion. Here is how:

First, remember that you read the array from left to the right. If you maintain a stack of integers with increasing order, you got this guaranteed:

For the bar of stack top i, its left extended exclusive border is the bar of stack i - 1, i.e. the 2nd largest element.

Thus, you can keep constructing the stack until encountering an element that breaks the increasing order.

This breaker element is then, of course, the right extended exclusive border of each bar in the stack.

Now, for each bar in the stack greater than the breaker element, you got its left and right ends to calculate the width, then the area. After the popings and the calculations, you can then push the breaker element back to the stack which fit into the increasing order with the remaining elements.

Q1

Wait, what if the stack has only one element? Does it mean: that element does not have an exclusive left end?

The answer is yes. If this single element is greater than the incoming element, the incoming element cannot get into the stack because it breaks the order. After this single element is poped, the breaker will then be pushed into the stack. Given that the breaker is smaller than the previous poped element, if the previous poped element can extend to the leftist 0 position, then the break can do as well.

public class Solution {
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        if (height.length == 0) return 0;
        
        Stack<Integer> increasingPositions = new Stack<>();
        int area = 0;
        for(int currentPos = 0; currentPos <= height.length; currentPos++) {
            int columnHeight = currentPos == height.length
                            ? 0
                            : height[currentPos];
            while (!increasingPositions.isEmpty() && 
                height[increasingPositions.peek()] > columnHeight) {
                    int h = height[increasingPositions.pop()];
                    int spannedWidth = increasingPositions.isEmpty()
                                    // see Q1, currentPos is the exclusive end. No exclusive start. All left bars included
                                    ? currentPos
                                    // FORMULA: exclusive end - exclusive start - 1 = spanned length
                                    : currentPos - increasingPositions.peek() - 1;
                    area = Math.max(area, h * spannedWidth);
                }
            increasingPositions.push(currentPos);
        }
        return area;
    }
}