7

leetcode之Largest Rectangle in Histogram

 3 years ago
source link: https://blog.csdn.net/yanxiangtianji/article/details/8575070
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

原载于http://blog.csdn.net/yanxiangtianji

转载请注明出处

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.

穷举各个segment，共二分之n平方个（O(n^2)），在每个segment里面找到最小高度（O(n)），可以优化到O(1)。找高度与segment长度之积最大的。

总体时间复杂度为O(n^3)，可以优化到O(n^2)；空间复杂度O(1)。

优化后（O(n^2)）：

方法一：可以将高度离散化为至多n个从0开始的“逻辑高度”（用real_height[h]表示逻辑高度h对应的真实高度），状态为到p为止的逻辑高度为h的矩形的面积f(p,h)，若这样的矩形不存在，则f(p,h)=0。
初始化假定f(-1,*0)=0
状态转移方程：
f(p,h)= 当h>height[p]时：0
             当h<=height[p]时：f(p-1,h)+h
最后求最大的f(n-1,*)，然后将逻辑高度表示的逻辑面积转换为实际面积：f(n-1,h)/h*real_height[h]。
时间复杂度O(n^2)，空间复杂度O(n^2+n)，考虑到更新f(p,*)时只用到了f(p-1,*)，可以将二维状态压缩为一维，即空间复杂度可以压缩为O(n)。
具体压缩方法（用dp表示f）：
直接去掉p维度，变f(p,h)为dp[h]，操作时更新对应的dp[h]即可。
如果能够知道：到p为止(p=0,1,...,n-1)，向前追溯l个格子（l=1,2,...,p）的矩形的最大高度f(p,l)，就可以用l*f(p,l)表示这个矩形的面积。

目标即为找到最大的l*f(p,l)值。其中p=1...n；l=1...p。

状态转移方程：

f(p,l) =  当l不为1：min( f(p-1,l-1), height[p] )

              当l为1：height[p]

时间复杂度O(n^2)；空间复杂度为O(n^2)，考虑到只是用了f(p-1,*)，空间可以压缩到O(n)。

具体压缩方法（用dp表示f）：

去掉p这个维度，l从大到小迭代，此时访问dp[l-1]即为访问f(p-1,l-1)。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK