Largest Rectangle in Histogram

LargestRectangleinHistogram.java

/**
 * 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) {
        Stack<Integer> s = new Stack<Integer>();
        if(height == null || height.length == 0)
            return 0;
        // Initialize max area
        int max_area = 0;
        int i = 0;
        // run through all bars of given histogram
        while(i < height.length) {
            // If current bar is higher than the bar of the stack peek, push it to stack. 
            if(s.empty() || height[s.peek()] <= height[i])
                s.push(i++);
            else {
                // if current bar is lower than the stack peek, calculate area of rectangle with stack top as the smallest bar.
                // 'i' is 'right index' for the top and element before top in stack is 'left index'
                int top = s.pop();
                // calculate the area with height[top] stack as smallest bar and update max_area if needed
                max_area = Math.max(max_area, height[top] * (s.empty() ? i : i - s.peek() - 1));
            }
        }
        // Now pop the remaining bars from stack and calculate area with every popped bar as the smallest bar.
        while(!s.isEmpty()) {
            int top = s.pop();
            max_area = Math.max(max_area, height[top] * (s.empty() ? i : i - s.peek() - 1));
        }
        return max_area;
    }
}