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.

histogram

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

histogram_area

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.

这题O(n^2)的解法比较容易,而且有好几种:
1.对于每一个height,遍历前面所有的height,求取面积最大值。即对于直方图的每一个右边界,穷举所有的左边界。将面积最大的那个值记录下来。
这样可以过小数据,但是大数据超时。因为这个解法包含了很多重复计算。一个简单的改进,可以通过选择合适的右边界,做一个剪枝(Pruning)。观察发现当height[k] >= height[k-1]时,无论左边界是什么值,选择height[k]总会比选择height[k-1]所形成的面积大。因此,在选择右边界的时候,首先找到一个height[k]小于height[k-1]的k,然后取k-1作为右边界,穷举所有左边界,找最大面积。

2.从每一个bar往两边走,以自己的高度为标准,直到两边低于自己的高度为止,然后用自己的高度乘以两边走的宽度得到矩阵面积。因为我们对于任意一个bar都计算了以自己为目标高度的最大矩阵,所以最好的结果一定会被取到。每次往两边走的复杂度是O(n),总共有n个bar,所以时间复杂度是O(n^2)。

对于网上的最优解法,可以达到O(n)的时间复杂度,非常巧妙:
我们要维护一个栈,栈内存储的是高度递增的下标。对于每一个直方图高度,分两种情况。1:当栈空或者当前高度大于栈顶下标所指示的高度时,当前下标入栈。否则,2:当前栈顶出栈,并且用这个下标所指示的高度计算当前矩形的面积。要计算面积,高度有了,宽度是什么呢?有两种情况,如果stack不为空,那么宽度是刚才出栈的index对应的位置到现在遍历到的矩形的位置。如果为空,则表示之前所有的bar都高于当前的bar,此时宽度就直接等于i。
最后,有一种可能是遍历结束了,但是stack不是空,所以还要把stack里面的内容再做一次上面的操作,处理干净。

public int largestRectangleArea(int[] height) {
    if(height==null || height.length==0)
        return 0;
    int max = 0;
    LinkedList<Integer> stack = new LinkedList<Integer>();
    for(int i=0;i<height.length;i++)
    {
        while(!stack.isEmpty() && height[i]<=height[stack.peek()])
        {
            int index = stack.pop();
            int curArea = stack.isEmpty()?i*height[index]:(i-stack.peek()-1)*height[index];
            max = Math.max(max,curArea);
        }
        stack.push(i);
    }
    while(!stack.isEmpty())
    {
        int index = stack.pop();
        int curArea = stack.isEmpty()?height.length*height[index]:(height.length-stack.peek()-1)*height[index];
        max = Math.max(max,curArea);            
    }
    return max;
}

感觉网上对此题的解答很多人都说不到重点上,都是人云亦云,估计有人都没搞明白细节就直接发帖了。也难怪,确实不好解释,费了我很长时间才明白到底上面的代码在干什么。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s