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;
	}
}