84. Largest Rectangle in Histogram Leetcode 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.

Solution:

The brute force method is to find the maximum width(search its left and right till a bar is lower than itself) for each bar in the array, eg. the maximum width for the given height[2,1,5,6,2,3] is [1,6,2,1,4,1], and then we can calculate the maximum area, which is 5*2=10. Time complexity is O(n^2). Constant space.

An efficient algorithm is use a stack to track the left boundaries. The basic idea, is if current value is bigger than the top value of the stack, which means the current value is not the right boundary of the top value, push the current value to the stack, otherwise, the current value is the right boundary of the top value, pop out the top value let's say h, since the stack is well ordered during this process, the next top element of the stack will be the left boundary of last top value, so we can calculate the area for this bar since we have the  height h, and we can calculate the width since we have the both left and right boundary of this height. Update the result if needed.

Tips: Two corner cases: 1. when stack is empty, which means the left boundary is -1;

                        2. After the iteration, if the stack is not empty, have to process the stack until it becomes empty, the right boundary will be the height.length,

 public int largestRectangleArea(int[] height) {  
   if(height==null || height.length==0) return 0;  
   Stack<Integer> st=new Stack<Integer>();  
   int res=0;  
   for(int i=0;i<height.length;i++){  
       while(!st.isEmpty() && height[i]<=height[st.peek()]){  
         int h=height[st.pop()];  
         int w=(st.isEmpty())? i:i-st.peek()-1;  
        res=Math.max(h*w,res);   
       }  
       st.push(i);   
     }  
    while(!st.isEmpty()){  
      int h=height[st.pop()];  
      int w=(st.isEmpty())? height.length:height.length-st.peek()-1;  
      res=Math.max(h*w,res);  
    }  
    return res;  
   }