Leetcode: 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.

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:

最容易和直接的解法是穷举法，对于直方图的每一个右边界，穷举所有的左边界。将面积最大的那个值记录下来。时间复杂度为O(n^2). 单纯的穷举在LeetCode上面过大集合时会超时。

优化解法：选择合适的右边界，skip没有意义的右边界。观察发现当height[k+1] >= height[k]时，无论左边界是什么值，选择height[k+1]总会比选择height[k]所形成的面积大。因此，在选择右边界的时候，首先找到一个height[k] > height[k+1 ]，然后取k 作为右边界，穷举所有左边界，找最大面积。值得注意的一点是一些特殊情况 such as 所有直方图是升序。此解法可以通过leetcode all test cases.

	public int largestRectangleArea(int[] height) {
	int maxArea = 0;
	int minHeight= 0;
	if(height.length == 0) return 0;
	if(height.length == 1) return height[0];
	int len = height.length;
	int i;
	for(i=0; i<len-1; i++){
	if(height[i]>height[i+1]){//find a valid right boundary
	minHeight = height[i];
	for(int j=i; j>=0; j--){
	minHeight = Math.min(minHeight, height[j]);
	maxArea = Math.max(maxArea, minHeight * (i-j+1));
	}
	}
	}
	if(i== len-1){
	minHeight = height[i];
	for(int j=i; j>=0; j--){
	minHeight = Math.min(minHeight, height[j]);
	maxArea = Math.max(maxArea, minHeight * (i-j+1));
	}
	}
	return maxArea;
	}

view raw gistfile1.java hosted with ❤ by GitHub

最后一个解法，时间复杂度为O(n)，利用一个stack存储高度递增的下标。这个方法的核心是：不仅选择合适的右边界，同时也选择合适的左边界，skip不必要的边界选择
对于每一个直方图高度，分两种情况。1：当栈空或者当前高度大于栈顶下标所指示的高度时，当前下标入栈。否则，2：当前栈顶出栈，并且用这个下标所指示的高度计算面积。而这个方法为什么只需要一个栈呢？因为当第二种情况时，for循环的循环下标回退，也就让下一次for循环比较当前高度与新的栈顶下标所指示的高度，注意此时的栈顶已经改变由于之前的出栈。

	public int largestRectangleArea(int[] height) {
	int area = 0;
	java.util.Stack<Integer> stack = new java.util.Stack<Integer>();
	for (int i = 0; i < height.length; i++) {
	if (stack.empty() || height[stack.peek()] < height[i]) {
	stack.push(i);
	}
	else {
	int start = stack.pop();
	int width = stack.empty() ? i : i - stack.peek() - 1;
	area = Math.max(area, height[start] * width);
	i--;
	}
	}
	while (!stack.empty()) {
	int start = stack.pop();
	int width = stack.empty() ? height.length : height.length - stack.peek() - 1;
	area = Math.max(area, height[start] * width);
	}
	return area;
	}

view raw gistfile1.java hosted with ❤ by GitHub

还有一个注意的点就是 width = stack.empty() ? i : i - stack.peek() - 1

Reference: http://blog.csdn.net/abcbc/article/details/8943485
                  http://www.geeksforgeeks.org/largest-rectangle-under-histogram/