绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
LeetCode 84 | 单调栈解决最大矩形问题
2020-07-06 00:35:10

今天是LeetCode专题第52篇文章,我们一起来看LeetCode第84题,Largest Rectangle in Histogram(最大矩形面积)。

这道题的官方难度是Hard,点赞3581,反对只有80,通过率在34.7%左右。从通过率上来看,难度其实还可以,并没有特别大,但是这道题的点赞比很高,说明题目的质量很好。实际上也的确如此,这题非常经典,我个人也非常推荐。建议大家有能力的都做一下本题,一定会很有收获。


题意

假设我们有一系列宽度相同都为1的矩形竖直地摆放在一起,请问摆放而成的这个图案所能围成的最大矩形的面积是多少?


比如上图当中,我们有6个矩形,它们的宽度都是1。我们能找到的最大矩形应该是中间5和6围成的矩形:


题目给定一个含有若干个整数的数字,表示这些矩形的高度,要求返回能找到的面积最大的矩形的面积。

样例

Input: [2,1,5,6,2,3]
Output10


区间求最值

拿到手应该能感受到这题的难度,我们一上来的确没有什么太好的思路,题目也比较明确,没有太多可以分析的入手点。所以我们可以先来思考一下最简单的解法。

最简单的解法就是找出能够围成的所有矩形,然后比较它们之间的面积,得出其中的最大面积。我们很容易可以想到可以遍历矩形的起始位置,这样就得到了矩形的宽。至于矩形的长也很简单,就是选定的这个区间段里的最低高度

我们可以做一个小小的思路转换,假设这些矩形都是木条,我们是要选出木条来制作木桶。那么根据木桶效应,木桶围成的水的高度取决于最短的那根木条,同样围成矩形的面积的高取决于这些矩形当中最矮的那个。也就是说,当我们确定了区间之后,我们只需要找到区间里最小的数就可以了。所以这题就转化成了区间求最值的问题,比如上图当中,如果我们选择最后三个矩形,那么它的高度就是2。

我们假设一共有n个长条矩形可供选择,那么我们可以选出的首尾组合就是,大概是n的平方量级个区间。对于每个区间,我们需要遍历它们中的元素获取最小值,这需要的遍历时间,所以整体的复杂度应该在量级。显然这是一个非常大的数量级,当n超过1000就很难计算出解了。

这个思路显然不够好,我们想要对它进行优化也不容易。比如说如果你学过线段树这类的数据结构,可能还会想到使用线段树,我们可以将每次求最小值的查询优化到,但即便如此最终的复杂度也很高。这是因为我们遍历区间首尾位置就耗费了,而这是很难优化的。所以这个思路的极限已经确定了,我们无法做出大的优化

从这点出发,如果存在更好的解法,那么一定不是通过这种方式进行的。


逆向思维

上面的一种思路虽然不太可行,但是它提供了一种正向思路。我们搜索所有的区间,然后通过区间里的木条确定区围成矩形的高度,就得到了矩形的面积。

既然这条路走不通,我们能不能反向思考呢?我们假设我们找到了答案,它是区间[a, b]段的木条围成的矩形,它的高度是h。那么根据木桶效应,a到b区间段的木条当中一定有一根的长度是h。比如下图当中[5, 6, 2, 3]如果要围成矩形,那么高度只能是2。


既然如此,我们可以
寻找以某根木条为短板所能构成的最大矩形比如上图当中,如果我们以第一根木条去寻找,就只能找到它本身,所以这个矩形的面积就是1 x 2 = 2。如果以第二根木条为短板去寻找,可以找到整个区间,它对应的面积就是1 x 6 = 6。

因为我们只有n个木条,以每个木条为短板寻找最大矩形,那么我们一定可以找出最多n个矩形。最终的答案一定在这n个矩形当中,在正向思维当中我们寻找木条区间需要的复杂度,然而我们寻找短板,只需要,也就是说这种思路的搜索空间更小,只要我们保证搜索的效率,就可以更快地找到答案。

为了找到每个木条对应的最大矩形,我们需要找到每个短板向左以及向右能够延伸到的最远位置。比如上图例子当中,根据每个木条向右延伸的最远位置,我们可以得到[0, 5, 3, 3, 5, 5],同样,我们可以得到每根木条向左延伸的数组:[0, 0, 2, 3, 2, 5]。有了这两个数组之后,我们就可以计算出以每一根木条为短板的最大矩形的面积,在这其中面积最大的那个就是答案。

这个位置我们可以使用单调栈来求,我们用一个有序的栈来维护延伸的位置。举个例子,我们用从栈底往栈顶递增的单调栈来维护每根木条向右延伸的位置。当我们遇到一根新的木条时,会弹出栈中所有比它大的值。对于这些值来说,这根新的木条就是它的右边界。比如[5, 6, 2],一开始读到5,入栈。接着读到6,由于6大于栈顶的5,所以6入栈。最后读到2,由于2比6小,所以6出栈,对于6来说,2的位置就是它的右侧边界。正是由于2比它小,所以它才需要出栈,也说明了2的左侧的元素都比6来的大,否则6在之前就应该出栈了。同理,2也是5的右侧边界。

如果你不了解单调栈,可以参考一下之前的文章:

LeetCode42题,单调栈、构造法、two pointers,这道Hard题的解法这么多?

我们把以上的逻辑翻转,就得到了左侧边界求解的逻辑。左右边界有了之后,我们只需要乘上它们之间的区间长度就得到了矩形的面积。

接着,我们来写出代码:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
  # 左侧边界初始化为
        left_side = [ for i in range(n)]
        # 右侧边界初始化为n-1
        right_side = [n-1 for _ in range(n)]
        
        stack_left = []
        stack_right = []
        
        for i in range(n):
            h = heights[i]
            # 弹出栈中所有比当前元素小的值
            # 注意,栈内存储的是下标
            while len(stack_right) >  and h < heights[stack_right[-1]]:
                tail = stack_right[-1]
                stack_right.pop()
                right_side[tail] = i - 1
            
            # 当前元素入栈
            stack_right.append(i)
            
            # 把坐标翻转,等价于逆向遍历
            i_ = n - 1 - i
            h = heights[i_]
            
            # 维护单调栈的逻辑同上
            while len(stack_left) >  and h < heights[stack_left[-1]]:
                tail = stack_left[-1]
                stack_left.pop()
                left_side[tail] = i_ + 1
                
            # 当前元素入栈
            stack_left.append(i_)
                

        ret = 
        for i in range(n):
            # 矩形面积等于右侧边界-左侧边界+1 x 高度
            cur = (right_side[i] - left_side[i] + 1) * heights[i]
            ret = max(ret, cur)
        return ret


总结

想要把这道题做出来,单单理清楚题意和单单会单调栈都是没有用的。既需要理清楚题意,从最简单的解法出发推导出优化的方法,也需要深刻理解单调栈这个数据结构,才可以灵活应用。

另外,在代码当中需要特别注意边界的情况。比如初始化时左右边界的设定,以及可能会出现连续相等元素的情况,这些都需要纳入考虑。代码虽然看起来简单,但是隐藏了很多细节,所以只看代码是没用的,最好还是能亲自实现一下。

分享好友

分享这个小栈给你的朋友们,一起进步吧。

TechFlow
创建时间:2020-03-19 11:13:43
机器学习、算法与数据结构、大数据相关和Python。 从纯基础开始的算法领域入门以及进阶内容。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • chengycz
    栈主

小栈成员

查看更多
  • 兔子爱喝红茶
  • 小雨滴
  • ITPUB学院
  • 栈栈
戳我,来吐槽~