LeetCode:Largest Rectangle in Histogram

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.

public class Solution {
    public int largestRectangleArea(int[] height) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(height==null) return 0;
        int[] left = new int[height.length],
              right = new int[height.length];
        for(int i=0;i<height.length;i++){
    if(i==0||height[i]>height[i-1]) left[i]=i;
else{
     int j=left[i-1]-1;
     while(j>=0 && height[j]>=height[i]) j--;
     left[i]=j+1;
} 
        }
        for(int i=height.length-1;i>=0;i--){
    if(i==height.length-1||height[i]>height[i+1]) right[i]=i;
else{
     int j=right[i+1]+1;
     while(j<height.length && height[j]>=height[i]) j++;
     right[i]=j-1;
} 
        }    
       int res=0;
        for(int i=0;i<height.length;i++){
    res=Math.max(res,(right[i]-left[i]+1)*height[i]);
        }
        return res;
   }
}

public class Solution {
    public int largestRectangleArea(int[] height) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Stack<Integer[]> scan = new Stack<Integer[]>();
        int res=0;
        for(int i=0;i<height.length;i++){
            if(i==0||height[i]>height[i-1]){
                Integer[] temp = new Integer[2];
                temp[0]=height[i];
                temp[1]=i;
                scan.push(temp);
            }else if(height[i]<height[i-1]){
                int a= 0;
                while(!scan.isEmpty()){
                     Integer[] temp=scan.pop();
                    if(temp[0]>height[i]){
                        res = Math.max(res,temp[0]*(i-temp[1]));
                        a=temp[1];
                    }else{
                        scan.push(temp);
                        break;
                    }
                }
                if(scan.isEmpty() || (scan.peek())[0]<height[i]){
                     Integer[] temp=new Integer[2];
                     temp[0]=height[i];
                     temp[1]=a;
                     scan.push(temp);
                }
            }    
        }
        while(!scan.isEmpty()){
            Integer[] temp=scan.pop();
            res = Math.max(res,temp[0]*(height.length-temp[1]));
        }
        return res;
    }
}