[leetcode]Largest Rectangle in Histogram

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.

这个算法是从网上看的，这里有详细的debug步骤，可以帮助大家了解整个算法思想。

 

 

 public int largestRectangleArea(int[] height) {
			if(height == null || height.length == 0){
				return 0;
			}        
			
			int[] copy = new int[height.length + 1];
			copy = Arrays.copyOf(height, height.length + 1);
			Stack<Integer> stack = new Stack<Integer>();
			int maxArea = 0;
			int i = 0;
			while(i < copy.length){
				if(stack.isEmpty() || copy[stack.peek()] <= copy[i]){
					stack.push(i++);
				}else{
					int num = stack.pop();
					maxArea = Math.max(maxArea,copy[num] * (stack.isEmpty() ? i : i - stack.peek() - 1));
				}
			}
	    	return maxArea;
	    }

 程序中最让人费解的就是这两句：

 

if(stack.isEmpty() || copy[stack.peek()] <= copy[i])stack.push(i++);

1. stack为空可以理解，但是为什么copy[stack.peek()] <= copy[i]也要压栈呢？

还有这一句：

maxArea = Math.max(maxArea,copy[num] * (stack.isEmpty() ? i : i - stack.peek() - 1));

其实这一句debug的时候就可以理解了。

 

不过po主并没有解答这两个疑惑。这里我做一个简单的小结：

以为例。

首先来看第二个问题：已知栈中有[1,5,6]遇到了2，则将栈顶元素6弹出，计算出面积为6

【(i - stack.peek() - 1) * 6】然后根据条件还需要弹栈，第二次弹栈计算出面积为10。遇到1时发现不能达到弹栈要求。

这里是第一个问题：为什么1就不能继续弹了？

答：因为弹了也白弹：由[1,5,6]组成的面积一定会小于[1,5,6,2]组成的面积，因此这里对2选择压栈，只有这样，才有可能组成更大的矩型，不过原程序中的要求是copy[stack.peek()] <= copy[i]压栈，其实copy[stack.peek()] < copy[i]严格的小于也是可以的，不过是多做了一步多余的计算。

 

因此第一个问题copy[stack.peek()] <= copy[i]其实是由两个问题合并组成的：

第一次是对于递增的元素进行压栈，因为只有这样才可能使矩形面积越来越大；

第二次是弹栈，弹到1的时候，对2进行压栈，这样做类似于一种剪枝，因此没有必要继续弹了，当然选择继续弹栈也是完全可以的，不过都是多余的而已。

 

第二个问题只是简单的对于面积进行更新，不过代码中很巧妙的用了stack.isEmpty ? i : i - stack.peek() - 1因为copy数组开大了一个空间，即：数组最后有一个哨兵元素0。才使得有了这个形式不变式，是厉害。

 

总之这道题算法实在是太巧妙了！但是感觉这种算法完全是技巧型的，不容易归纳。