[LeetCode] Largest Rectangle in Histogram

Problem:

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:O(n)

public class Solution {
    public int largestRectangleArea(int[] height) {
        if ( height==null||height.length==0){
            return 0;
        }

        Stack<Integer> stack=new Stack<Integer>();        
        int max=0;
        int i=0;
        
        while(i<height.length){
            if (stack.isEmpty()||height[i]>=height[stack.peek()]){
                stack.push(i);
                i++;
            }
            else{
                int h=height[stack.pop()];
                int wid=stack.isEmpty()?i:i-stack.peek()-1;
                max=Math.max(h*wid, max);
            }   
        }
        
        while (!stack.isEmpty()){
            int h=height[stack.pop()];
            int wid=stack.isEmpty()?i:i-stack.peek()-1;
            max=Math.max(h*wid, max);
        }
        
        return max;
    }
}

Key Concept:Using stack to store increasing index