Largest Rectangle in Histogram | Leetcode

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.

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

---

Solution: This unfortunately is a hard to understand algorithm. I would not be able to know this algorithm without knowing it in advance.

The general idea is that we will keep a running stack. When the current bar is equal to or taller than the last bar in the stack, then we will push it into the stack. If not, we will try to exhaust down the stack until the stack is empty or the current bar in the stack is equal to or taller than the last bar in the stack.

For each time we exhaust the stack, we take out the top element. We take the height of this element to calculate the area of the rectangle. Then we try to get the width of the rectangle. When the stack is empty, we take the width as the index of the current bar, which is the width from the beginning until the bar right before the current bar. Else we take the width as "i - stack.peek() - 1", which is the width until the top element in the stack but excluding that top element.

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;
        
        do {
            // Exhaust the stack while the current bar is lower than the next one.
            while (!stack.isEmpty() && (i == height.length || height[i] < height[stack.peek()])) {
                // Get the height of the last bar.
                int h = height[stack.pop()];
                
                // Get the width of the current rectangle.
                // If the stack is empty, then we go back to the first bar.
                // Else we go back to the last bar higher than the current one.
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                
                maxArea = Math.max(h * width, maxArea);
            }
            stack.push(i++);
        } while (i <= height.length);
        
        return maxArea;
    }
}