LeetCode 84: Largest Rectangle in Histogram

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.

public class Solution {
    public int largestRectangleArea(int[] height) {
        // For every bar 'x', we calculate the area with 'x' as the smallest bar in the rectangle.
        // If we calculate such area for every bar 'x' and find the maximum of all areas, our task is done.
        
        // How to calculate area with 'x' as the smallest bar?
        // We need to know indexes of left-x-first and right-x-first bars smaller than 'x', respectically.
        // Let us call these indexes as 'left index' and 'right index', respectively.
        // We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once.
        // A bar is popped from stack when a bar of smaller height is seen.
        // When a bar is popped, we calculate the area with the popped bar as smallest bar.
        
        // How do we get left and right indexes of the popped bar:
        // The current index tells us the 'right index' (i) and index of previous item in stack is the 'left index' (stack.peek()).
        
        // Step 1: Create an empty stack.
        // Step 2: Start from first bar, and do following for every bar 'height[i]' where 'i' varies from 0 to n-1.
        // Step 2.a: If stack is empty or height[i] is higher than the bar at top of stack, then push 'i' to stack.
        // Step 2.b: If height[i] is smaller than the top of stack,
        // then keep removing the top of stack while top of the stack is smaller than height[i].
        // Let the removed bar be height[tmp]. Calculate area of rectangle with height[tmp] as the smallest bar.
        // For height[tmp], the 'left index' is previous (stack.peek()) item in stack and 'right index' is 'i' (current index).
        // Step 3. If the stack is not empty, then one by one remove all bars from stack and do Step 2.b for every removed bar.
        Stack<Integer> stack = new Stack<>();
        
        int maxArea = 0;
        int i = 0;
        
        while (i < height.length)
        {
            if (stack.isEmpty() || height[i]>height[stack.peek()])
            {
                stack.push(i);
                i++;
            }
            else
            {
                int tmp = stack.pop();
                maxArea = Math.max(maxArea, height[tmp] * (stack.isEmpty() ? i : i-stack.peek()-1));
            }
        }
        
        // Don't miss the last bar as the smallest bar.
        // Special case: If "height" is an ascending array, the largest rectangle area is the area of last bar.
        while (!stack.isEmpty())
        {
            int tmp = stack.pop();
            maxArea = Math.max(maxArea, height[tmp] * (stack.isEmpty() ? i : i-stack.peek()-1));
        }         
        
        return maxArea;  
    }
}