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.

Solution 1: The best solution use O(n) time and stack. The idea is for given index i, let us see the max rectangle use height[i] as the height. Then the length should be determined but [left,right], left-1 will lower than heigh[i] and right+1 will be lower than height[i]. With this in mind, then use a stack store increasing element to solve it in O(n), details as below:

 public class Solution {  
   public int largestRectangleArea(int[] height) {  
     int n=height.length, res=0;  
     Deque<Integer> stack=new LinkedList<>();  
     for (int i=0; i<n; i++) {  
       while (!stack.isEmpty() && height[stack.peek()]>height[i]) {  
         int j=stack.pop();  
         int left=stack.isEmpty()?0:stack.peek()+1;  
         res=Math.max(res,height[j]*(i-left));  
       }  
       stack.push(i);  
     }  
     while (!stack.isEmpty()) {  
       int j=stack.pop();  
       int left=stack.isEmpty()?0:stack.peek()+1;  
       res=Math.max(res,height[j]*(n-left));  
     }  
     return res;  
   }  
 }