柱状图内最大的矩形面积 Largest Rectangle in Histogram @LeetCode

1 暴力法，TLE

2 很巧妙的用了两个stack，一个stack保存高度，另一个保存index

遍历height数组，

1 如果stack为空或者当前元素的高度大于height stack顶元素（前一个元素）的高度 => 把当前高度额index分别添加到两个stack顶

2 如果当前元素的高度等于height stack顶元素的高度 => 什么都不做

3如果当前元素的高度小于height stack顶元素的高度 => 持续弹栈直到当前元素的高度大于栈顶元素，并每次都计算面积（height * （current index - popped index）），保存最大面积。最后把当前高度和最后一个弹出的index（非当前index） 重新压入栈中

4 处理完height数组，如果stack非空，则一一弹栈并计算面积。

http://www.youtube.com/watch?v=E5C5W6waHlo

package Level5;

import java.util.Stack;

/**
 * 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.

http://www.leetcode.com/wp-content/uploads/2012/04/histogram.png
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

http://www.leetcode.com/wp-content/uploads/2012/04/histogram_area.png
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 S84 {

	public static void main(String[] args) {
		int[] height = {2,1,2};
		System.out.println(largestRectangleArea(height));
	}

	public static int largestRectangleArea(int[] height) {
		if(height.length == 0){
			return 0;
		}
		Stack<Integer> heightStack = new Stack<Integer>();
		Stack<Integer> indexStack = new Stack<Integer>();
		
		heightStack.push(height[0]);
		indexStack.push(0);
		
		int max = height[0];
		for(int i=1; i<height.length; i++){
			/*
			 #1: current Larger than previous (top of height stack)
			Push current height & index as candidate rectangle start position
			 */
			if(heightStack.isEmpty() || height[i] > heightStack.peek()){
				heightStack.push(height[i]);
				indexStack.push(i);
			}
			/*
			 #3: current is less than previous 
			Need keep popping out previous heights, and compute the candidate rectangle with height and width (current index MINUS previous index)
			Push the height and index (appropriate position) to stacks
			 */
			else if(height[i] < heightStack.peek()){
				int lastIndex = 0;	// used to keep track of last index which will be replacing the current index for current height inserting
				while(!heightStack.isEmpty() && height[i]<heightStack.peek()){
					lastIndex = indexStack.pop();
					int h = heightStack.pop();
					int w = i - lastIndex;
					max = Math.max(max, h*w);
				}
				heightStack.push(height[i]);
				indexStack.push(lastIndex);	// Here should be lastIndex, one example: [2,1,2] => if lastIndex:3, if i:2
			}
		}
		
		// deal with remaining elements in the stack
		while(!heightStack.isEmpty()){
			int lastIndex = indexStack.pop();
			int h = heightStack.pop();
			int w = height.length - lastIndex;
			max = Math.max(max, h*w);
		}
		
		return max;
	}
	
	// TLE
	public static int largestRectangleArea2(int[] height) {
		int max = 0;
		int len = height.length;
		for(int i=0; i<len; i++){
			int minHeight = height[i];
			for(int j=i; j<len; j++){
				minHeight = Math.min(minHeight, height[j]);
				max = Math.max(max, (j-i+1)*minHeight);
			}
		}
		return max;
	}

}