直方图的最大内接矩形

阅微客栈 » 头脑风暴

直方图的最大内接矩形

(9 posts)

发起于 1 年之前，作者 szuxjq
最新回复来自于 vvizard

Tags:

szuxjq
Member

据说有这么一道题：求直方图的最大内接矩形,假设每个细条的宽度为1。

发布于 1 年之前 #
zhang
神

这是某知名网络公司面试题，哈哈。

发布于 1 年之前 #
szuxjq
Member

这题好难啊，是不是要特别的数学知识？坛主给点思路如何？

发布于 1 年之前 #
zhang
神

用栈来做，最后均摊的时间复杂度O(1)，总体复杂度为O(n)

发布于 1 年之前 #
xiexiexx
Member

求直方图的最大内接矩形,假设每个细条的宽度为1。

初始输入为h[i]，即i处的细条高度值，i的范围是[0, n-1]。

定义：三元组(i, p, q)为一个矩形，高度为h[i]，宽度为q-p+1，即一个从p开始，在q结束的矩形。

max也是一个三元组，表示为(maxS, maxL, maxR)。

维护一个这样一个栈，右边为栈顶：

$(D_1,p_1,q_1), (D_2,p_2,q_2), ... , (D_r,p_r,q_r)$

其中 $h[D_1] <= h[D_2] <= ... <= h[D_r]$

且有 $q_i+1 = p_{i+1}$

初始情况stack为：

(0,0,0)

置i初始为1，当i<n时进行如下循环：

(1) 栈顶对应的 $h[D_r]$

若 $h[i] >= h[D_r]$

则把(i,i,i)推入栈，且i++；

(2) 栈顶对应的 $h[D_r]$

若 $h[i]< h[D_r]$

先弹出 $(D_r,p_r,q_r)$

如果 $h[D_r]*(q_r-p_r+1) > maxS$

则更新max为 $(h[D_r]*(q_r-p_r+1), p_r, q_r)$

操作完之后再分3种情况：

(2a) 栈不空，设当前栈顶为 $(D_{r-1},p_{r-1},q_{r-1})$

且 $h[D_{r-1}] >= h[i]$

执行如下操作：

修改栈顶为 $(D_{r-1},p_{r-1},q_r)$

修改后操作后i值不变。

(2b) 栈不空，设当前栈顶为 $(D_{r-1},p_{r-1},q_{r-1})$

且 $h[D_{r-1}] < h[i]$

执行如下操作：

把 $(h[i], p_r,i)$ 推入栈内，i++。

(2b) 栈为空，把 $(h[i], p_r,i)$ 推入栈内，i++。

上面的循环操作完毕后，留下的是一个不空的栈。

当栈不为空时进行如下循环：

当前栈顶所对应的是 $h[D_r]$

先弹出 $(D_r,p_r,q_r)$

如果 $h[D_r]*(q_r-p_r+1) > maxS$

则更新max为 $(h[D_r]*(q_r-p_r+1), p_r, q_r)$

操作完后如果栈不空，设前栈顶为 $(D_{r-1},p_{r-1},q_{r-1})$

修改栈顶为 $(D_{r-1},p_{r-1},q_{r-1})$

容易知道分摊复杂性是O(1)，所以算法的时间复杂度是O(n)，空间复杂度是O(n)。

发布于 1 年之前 #
xiexiexx
Member

把错误稍微改正一下：

三元组 $<i, p, q>$ 意味着它包含了一个高度为 $h[i]$ ，从 $p$ 到 $q$ 的矩形。
$max$ 也是一个三元组，表示为 $<maxH, maxL, maxR>$ ，记 $maxS$ 这个变量的值永远为 $maxH*(maxR-maxL+1)$ 。
$max$ 记录了最大的内接矩形。

$max$ 的定义还是与上面一样，也是记录着最大的内接矩形。

维护一个这样一个栈，右边为栈顶：

$<D_1,p_1,q_1>$ , $<D_2,p_2,q_2>$ , ... , $<D_r,p_r,q_r>$

其中 $h[D_1] <= h[D_2] <= ... <= h[D_r]$ ，且 $q_i+1 = p_{i+1}$ 。

实际上这个栈代表了当前还未考虑其内接矩形大小的一些相邻矩形。

初始情况栈为：

$<0,0,0>$

置 $i$ 初始为1，当 $i<n$ 时进行如下循环（可证每次开始循环时栈不空，此时栈顶元素为 $<D_r, p_r, q_r>$ ）：

(1) 若 $h[i] >= h[D_r]$ ，则把 $<i, i, i>$ 进栈，且 $i++$ ；

(2) 若 $h[i] <= h[D_r]$ ，先弹出 $<D_r, p_r, q_r>$ 。如果 $h[D_r]*(q_r-p_r+1) > maxS$ ，
则更新 $maxS = h[D_r]*(q_r-p_r+1)$ 且 $max = <h[D_r], p_r, q_r>$ 。操作完之后再分3种情况：

(2a) 栈不空，设当前栈顶为 $<D_{r-1}, p_{r-1}, q_{r-1}>$ ，且 $h[D_{r-1}] >= h[i]$ ：
先修改栈顶为 $<D_{r-1}, p_{r-1}, q_r>$ ，执行完操作后 $i$ 值不变。

(2b) 栈不空，设当前栈顶为 $<D_{r-1}, p_{r-1}, q_{r-1}>$ ，且 $h[D_{r-1}] < h[i]$ ：
把 $<h[i], p_r, i>$ 推入栈内， $i++$ 。

(2c) 栈为空，把 $<h[i], p_r, i>$ 推入栈内， $i++$ 。

上面的循环操作完毕后，留下的是一个不空的栈。

当栈不为空时进行如下循环：

当前栈顶所对应的 $h[D_r]$ ，先弹出 $<D_r, p_r, q_r>$ ，如果 $h[D_r]*(q_r-p_r+1) > maxS$ ，
则更新 $maxS = h[D_r]*(q_r-p_r+1)$ 且 $max$ 为 $<h[D_r], p_r, q_r>$ 。
操作完后如果栈不空，设前栈顶为 $<D_{r-1},p_{r-1},q_{r-1}>$ ，修改栈顶为 $<D_{r-1}, p_{r-1}, q_r>$ 。

容易知道分摊复杂性是O $(1)$ ，所以算法的时间复杂度是O $(n)$ ，空间复杂度是O $(n)$ 。

发布于 1 年之前 #
xiexiexx
Member

效率微调：可以在程序的进行中把一些高度相同的矩形直接合并成一个，不去比较与 $maxS$ 的大小，等待下次比较，
因为这样得到的矩形更大且不违反高度的约束。这是一种Lazy Method，很有效。

栈中 $h[D_1] < h[D_2] < ... < h[D_r]$ 。循环语句做一些调整：

置 $i$ 初始为1，当 $i<n$ 时进行如下循环（可证每次开始循环时栈不空，此时栈顶元素为 $<D_r, p_r, q_r>$ ）：

(1) 若 $h[i] > h[D_r]$ ，则把 $<i, i, i>$ 进栈，且 $i++$ ；

(2) 若 $h[i] == h[D_r]$ ，则把栈顶修改为 $<D_r, p_r, i>$

(2) 若 $h[i] < h[D_r]$ ，先弹出 $<D_r, p_r, q_r>$ 。如果 $h[D_r]*(q_r-p_r+1) > maxS$ ，
则更新 $maxS = h[D_r]*(q_r-p_r+1)$ 且 $max = <h[D_r], p_r, q_r>$ 。操作完之后再分4种情况：

(2a) 栈不空，设当前栈顶为 $<D_{r-1}, p_{r-1}, q_{r-1}>$ ，且 $h[D_{r-1}] > h[i]$ ：
修改栈顶为 $<D_{r-1}, p_{r-1}, q_r>$ ，执行完操作后 $i$ 值不变。

(2b) 栈不空，设当前栈顶为 $<D_{r-1}, p_{r-1}, q_{r-1}>$ ，且 $h[D_{r-1}] == h[i]$ ：
直接修改栈顶为 $<D_{r-1}, p_{r-1}, i>$ ，再执行 $i++$ 。

(2c) 栈不空，设当前栈顶为 $<D_{r-1}, p_{r-1}, q_{r-1}>$ ，且 $h[D_{r-1}] < h[i]$ ：
先把 $<h[i], p_r, i>$ 推入栈内，再执行 $i++$ 。

(2d) 栈为空，把 $<h[i], p_r, i>$ 推入栈内， $i++$ 。

上面的循环操作完毕后，留下的是一个不空的栈。

当栈不为空时进行如下循环：

当前栈顶记为 $<D_r, p_r, q_r>$ 。先弹出栈顶元素。若 $h[D_r]*(q_r-p_r+1) > maxS$ ，
则更新 $maxS = h[D_r]*(q_r-p_r+1)$ 且 $max = <h[D_r], p_r, q_r>$ 。
操作完后如果栈不空，设当前栈顶为 $<D_{r-1}, p_{r-1}, q_{r-1}>$ ，修改栈顶为 $<D_{r-1}, p_{r-1}, q_r>$ 。

发布于 1 年之前 #
qqpeter
Member

不错

发布于 1 年之前 #
vvizard
Member

所要的这个最大的矩形可能与直方图的底线只有一个公共点。

楼主考虑到这个问题了么？

发布于 11 月之前 #

该主题的 RSS Feed

你必须登录后发帖。

阅微客栈

阅微客栈 » 头脑风暴

直方图的最大内接矩形

回复