Largest Rectangle in Histogram

We need to find the maximum area of the rectangles. For a given rectangle, it can only form a rectangle larger than it's size when the consecutive rectangles have less or equal height. So if we use a stack to store all previous rectangles that have a larger height than the current one, we can find the maximum rectangle that is in the stack.

Let's go through it with the example shown in the graph.

Since i will also serve a row as the width of the rectangle, the iteration should go from 0 to the height.length.

i = 0, stack is empty, stack.push(0).
i = 1, curr < height[0], max = the area of rectangle 0, stack.push(1).
from i = 2 to 4, the height of the rectangle is increasing, the largest rectangle may be height[1] * 5 height[2] * 4 ... height[4] * 1, we store i -s in the stack.
i = 5, now curr (height[5]) < height[4], we calculate the area of each rectangle and find the maximum.
Note i = 1 is still in the stack because it is smaller than curr, which means it may form larger rectangle with next several rectangles (e.g., the red rectangle when i = 6).
When i = 7, since we want to count the last rectangle, we assume curr = -1 which is always smaller than any height[i].

public class MaxRectangle {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        
        Stack stack = new Stack();
        int max = 0;
        for (int i = 0; i <= height.length; i++)
        {
            int curr = (i == height.length) ? -1 : height[i];
            while (!stack.isEmpty() && curr <= height[stack.peek()])
            {
                int h = height[stack.pop()];
                // last element in the stack is the rectangle with the shortest height, thus the area of rectangle is 
                // i * height
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        return max;
        
    }
}