Largest Rectangle in Histogram (Java)

LeetCode

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:

similar questions(Longest Valid Parentheses, Maximal Rectangle)

Maintain a stack which used to record bar's indexes, in order to reach max increasing  bars until an shorter bar come,  then we calculate the  area of each situation consist by the bars in our stack. Because there may a coupe bars left in our stack, so don't forget calculate  them after first while loop.  

	public class LargestRectangleInHistogram {
	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;
	}
	}

view raw LargestRectangleInHistogram.java hosted with ❤ by GitHub