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

	package leetcode.array;
	import java.util.Stack;
	/**
	* Solution 1: O(n^2). 暴力
	* Solution 2: O(n)
	* stack 维护一个升序序列, 不管value 小的，从左扫一次，从右扫一次. maintain an incremental stack;
	* (1) if a[i] > stack top, push a[i] to stack.
	* (2) if a[i] <= stack top. keep poping element out from stack until the top of stack is smaller than current value.
	*
	* 1 3 4 new 2
	* 这样其实就是 1.能够知道以2往左走能到哪，就是到1 2. 到时候从右往左来一遍，就知道2往右能远能到哪，这样就知道current的面积了
	* 每次出栈时候计算，能到最左就是stack.peek() 最右就是 i.
	* 这里就不算从右往左那一遍了，直接碰到 current <= height[stack top] 就是能到的最右了，这时候算 stack top 为height的面积，
	* 不是所有的index都算一遍，只有降序的时候了才算
	*
	*
	* @author jeffwan
	* @date May 18, 2014
	*/
	public class LargestRectangleArea {
	public static void main(String[] args) {
	int[] height = {2,1,5,6,2,3};
	System.out.println(largestRectangleArea(height));
	}
	// O(n), every number push 1 time, pop 1 time.
	public static int largestRectangleArea(int[] height) {
	if (height == null || height.length == 0) {
	return 0;
	}
	Stack<Integer> stack = new Stack<Integer>();
	int max = 0;
	for(int i = 0; i <= height.length; i++) { // i == height.length, make sure calculate one more time till ends.
	int current = (i == height.length) ? -1 : height[i];
	while (!stack.isEmpty() && current <= height[stack.peek()]) {
	int h = height[stack.pop()];
	int w = stack.isEmpty()? i : i - stack.peek() - 1;
	max = Math.max(max, h * w);
	}
	stack.push(i);
	}
	return max;
	}
	}

view raw LargestRectangleArea.java hosted with ❤ by GitHub