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 heights = [2,1,5,6,2,3],
return 10.

This is a hard question. To solve This problem in linear time, use a stack to track the index of each number:

• if current value is great-equal than the top of stack. which means it is a increasing sequence,(The index at top don't need to be the previous of current), push the current index.
• If not, this means there is a small rectangle at the top of stack, pop the top of stack, the next top index and current index is the width of a found rectangle, and the height is the previous poped item.

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();// stack for index to caculate width.
        int max = 0;
        int i =0;
        while( i <= heights.length){
            int val = i < heights.length ? heights[i] : 0;
            if(stack.empty() || val >= heights[stack.peek()]){
                stack.push(i);
                i++;
            }else{
                int h = stack.pop();
                int w = stack.empty() ? i : i - stack.peek() -1;
                max = Math.max(max, heights[h] * w);
            }
        }

        return max;
    }
}