盛日辉的博客
0%

Leetcode-84柱状图的最大矩形-85最大矩形

发表于 更新于 分类于

题目

这里主要是记一下对 84 题灵神题解中的代码的理解。

三次遍历

这里主要抓住在最后遍历的时候，枚举的 $h$ 是矩形的高，$l$ 和 $r$ 是在这个高的情况下左右各可以到多远，开区间 $(l,r)$ 构成矩形的宽，就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left = [-1] * n
        st = []
        for i, h in enumerate(heights):
            while st and heights[st[-1]] >= h:
                st.pop()
            if st:
                left[i] = st[-1]
            st.append(i)

        right = [n] * n
        st.clear()
        for i in range(n - 1, -1, -1):
            h = heights[i]
            while st and heights[st[-1]] >= h:
                st.pop()
            if st:
                right[i] = st[-1]
            st.append(i)

        ans = 0
        for h, l, r in zip(heights, left, right):
            ans = max(ans, h * (r - l - 1))
        return ans

两次遍历

在上面方法中 $left$ 的遍历中，弹出栈顶的条件是：$h <= 栈顶$ ，而 $h$ 一定是在栈顶的右边（后遍历到），所以，弹出栈顶的这个动作，其实蕴含着，$h$ 是栈顶右边最近的小于等于它的柱子。

因此，我们就可以在遍历 $left$ 的同时构造出 $right$ ，只不过 $right[i]$ 表示的是 $h = height[i]$ 右边最近的小于等于它的柱子，不再只是小于了。

这个定义的转变不需要改变其他以及不会影响结果。原因如灵神题解里所说，在一些相同高度的柱子里，虽然左边的的柱子的 $right$ 可能会变小，但最右边的那个不会变，而它的面积也不会变，所以不会影响结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left = [-1] * n
        right = [n] * n
        st = []
        for i, h in enumerate(heights):
            while st and heights[st[-1]] >= h:
                # 栈顶的柱子的右边最近的小宇等于它的就是 i 位置的柱子
                right[st.pop()] = i
            if st:
                left[i] = st[-1]
            st.append(i)

        ans = 0
        for h, l, r in zip(heights, left, right):
            ans = max(ans, h * (r - l - 1))
        return ans

一次遍历

在三次到两次的过程中，我们挖掘了栈顶的信息使得在一次遍历中同时得到了 $left$ 和 $right$， 那是否还有信息可以挖掘呢？比如在这个过程中，直接得到 $left[i]$ ，进而一次遍历就算出以 $heights[i]$ 为高的矩形的面积呢？

可以的。那便是，栈顶的下一个元素就是栈顶的 $left$ ，而由前面知道，栈顶的 $right$ 就是当前遍历的这个柱子，也就是说，现在的 $h$ 是栈顶，栈顶下面的是 $l$，当前遍历的是 $r$，开区间 $(l,r)$ 是宽。

代码实现时，可以在栈中先放一个 $-1$ ，用做最后一个柱子的 $l$ 。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(-1)  # 最后大火收汁，用 -1 把栈清空
        st = [-1]  # 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        ans = 0
        for right, h in enumerate(heights):
            while len(st) > 1 and heights[st[-1]] >= h:
                i = st.pop()  # 矩形的高（的下标）
                left = st[-1]  # 栈顶下面那个数就是 left
                ans = max(ans, heights[i] * (right - left - 1))
            st.append(right)
        return ans

第 85 题

这一题还想用前缀和呢，但灵神的想法真的是太妙了！！！

题解。