Largest Rectangle in Histogram

Problem : Given n nonnegative integers representing the histogram's bar height where the width of each bar is 1. find the area of largest rectangle in 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 Ex : Given height [2,1,5,6,2,3]

Return 10. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

public class Solution { public int largestRectangleArea(int[] height) { //if stack is empty or current height is greater than previous height, //push it in stack. // if height is equal ignore it. // if height is less than the previous height, keep popping heights //till you find a lesser height or stack is empty. //while popping calculate respective area and update max area. if(height == null || height.length <1){ return 0; } Stack index = new Stack(); Stack hStack = new Stack(); int maxArea =0; for(int i=0; i < height.length; i++){ if(hStack.isEmpty() || (int)hStack.peek() < height[i]){ hStack.push(height[i]); index.push(i); }else if((int)hStack.peek() > height[i]){ int lastIndex =0; while(!hStack.isEmpty() && (int)hStack.peek() > height[i]){ int hi = (int)hStack.pop(); int in = (int)index.pop(); lastIndex = in; int area = (i- in)* hi; if(area > maxArea){ maxArea = area; } } //push current height now hStack.push(height[i]); //push the last index of the height which was popped //beacouse area of rectangle including current height will //be counted from previous smaller rectangle. index.push(lastIndex); } } while(!hStack.isEmpty()){ int hi = (int)hStack.pop(); int in = height.length - (int)index.pop(); int area = in* hi; if(area > maxArea){ maxArea = area; } } return maxArea; } }