题目0084:柱状图中最大的矩形

题目描述

给定n个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为1。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

以上是柱状图的示例,其中每个柱子的宽度为1,给定的高度为[2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积,其面积为10个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

解题技巧

我们需要在柱状图中找出最大的矩形,因此我们可以考虑枚举矩形的宽和高,其中宽表示矩形贴着柱状图底边的宽度,高表示矩形在柱状图上的高度。

如果我们枚举宽,我们可以使用两重循环枚举矩形的左右边界以固定宽度w,此时矩形的高度h,就是所有包含在内的柱子的最小高度，对应的面积为w * h。下面给出了这种方法的C++代码。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int ans = 0;
        // 枚举左边界
        for (int left = 0; left < n; ++left) {
            int minHeight = INT_MAX;
            // 枚举右边界
            for (int right = left; right < n; ++right) {
                // 确定高度
                minHeight = min(minHeight, heights[right]);
                // 计算面积
                ans = max(ans, (right - left + 1) * minHeight);
            }
        }
        return ans;
    }
};

如果我们枚举高,我们可以使用一重循环枚举某一根柱子,将其固定为矩形的高度h。随后我们从这跟柱子开始向两侧延伸,直到遇到高度小于h的柱子,就确定了矩形的左右边界。如果左右边界之间的宽度为w,那么对应的面积为w * h。下面给出了这种方法的C++代码。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int ans = 0;
        for (int mid = 0; mid < n; ++mid) {
            // 枚举高
            int height = heights[mid];
            int left = mid, right = mid;
            // 确定左右边界
            while (left - 1 >= 0 && heights[left - 1] >= height) {
                --left;
            }
            while (right + 1 < n && heights[right + 1] >= height) {
                ++right;
            }
            // 计算面积
            ans = max(ans, (right - left + 1) * height);
        }
        return ans;
    }
};

可以发现,这两种暴力方法的时间复杂度均为 $O(N^2)$ ,会超出时间限制,我们必须要进行优化。考虑到枚举宽的方法使用了两重循环,本身就已经需要 $O(N^2)$ 的时间复杂度,不容易优化,因此我们可以考虑优化只使用了一重循环的枚举高的方法。

方法一:单调栈

我们归纳一下枚举高的方法：

首先我们枚举某一根柱子i作为高 $h = \textit{heights}[i]$ ;

随后我们需要进行向左右两边扩展,使得扩展到的柱子的高度均不小于h。换句话说,我们需要找到左右两侧最近的高度小于h的柱子,这样这两根柱子之(不包括其本身)的所有柱子高度均不小于h,并且就是i能够扩展到的最远范围。

那么我们先来看看如何求出一根柱子的左侧且最近的小于其高度的柱子。除了根据前言部分暴力地进行枚举之外,我们可以通过如下的一个结论来深入地进行思考:

对于两根柱子 $j_0$ 以及 $j_1$ ,如果 $j_0 < j_1$ 并且 $\textit{heights}[j_0] \geq \textit{heights}[j_1]$ ,那么对于任意的在它们之后出现的柱子i( $j_1 < i$ ), $j_0$ 一定不会是i左侧且最近的小于其高度的柱子。

换句话说,如果有两根柱子 $j_0$ 和 $j_1$ ,其中 $j_0$ 在 $j_1$ 的左侧,并且 $j_0$ 的高度大于等于 $j_1$ ,那么在后面的柱子i向左找小于其高度的柱子时, $j_1$ 会挡住 $j_0$ , $j_0$ 就不会作为答案了。

这样以来,我们可以对数组从左向右进行遍历,同时维护一个可能作为答案的数据结构,其中按照从小到大的顺序存放了一些j值。根据上面的结论,如果我们存放了 $j_0, j_1, \cdots, j_s$ ,那么一定有 $\textit{height}[j_0] < \textit{height}[j_1] < \cdots < \textit{height}[j_s]$ ,因为如果有两个相邻的j值对应的高度不满足<关系,那么后者会挡住前者,前者就不可能作为答案了。

当我们枚举到第i根柱子时,我们的数据结构中存放了 $j_0, j_1, \cdots, j_s$ ,如果第i根柱子左侧且最近的小于其高度的柱子为 $j_i$ ,那么必然有

$\textit{height}[j_0] < \textit{height}[j_1] < \cdots < \textit{height}[j_i] < \textit{height}[i] \leq \textit{height}[j_{i+1}] < \cdots < \textit{height}[j_s]$

这样我们就可以使用二分查找的方法找到i对应的 $j_i$ ,但真的需要吗?当我们枚举到i+1时,原来的i也变成了j值,因此i会被放入数据结构。由于所有在数据结构中的j值均小于i,那么所有高度大于等于 $\textit{height}[i]$ 的j都不会作为答案,需要从数据结构中移除。而我们发现,这些被移除的j值恰好就是 $j_{i+1}, \cdots, j_s$ 。

这样我们在枚举到第i根柱子的时候,就可以先把所有高度大于等于 $\textit{height}[i]$ 的j值全部移除,剩下的j值中高度最高的即为答案。在这之后,我们将i放入数据结构中,开始接下来的枚举。此时,我们需要使用的数据结构也就呼之欲出了,它就是栈。

栈中存放了j值。从栈底到栈顶,j的值严格单调递增,同时对应的高度值也严格单调递增:

当我们枚举到第i根柱子时,我们从栈顶不断地移除 $\textit{height}[j] \geq \textit{height}[i]$ 的j值。在移除完毕后,栈顶的j值就一定满足 $\textit{height}[j] < \textit{height}[i]$ ,此时j就是i左侧且最近的小于其高度的柱子。

这里会有一种特殊情况。如果我们移除了栈中所有的j值,那就说明i左侧所有柱子的高度都大于 $\textit{height}[i]$ ,那么我们可以认为i左侧且最近的小于其高度的柱子在位置j=-1,它是一根虚拟的、高度无限低的柱子。这样的定义不会对我们的答案产生任何的影响,我们也称这根虚拟的柱子为哨兵。

我们再将i放入栈顶。

栈中存放的元素具有单调性,这就是经典的数据结构单调栈了。

例子

我们用一个具体的例子[6, 7, 5, 2, 4, 5, 9, 3]来帮助读者理解单调栈。我们需要求出每一根柱子的左侧且最近的小于其高度的柱子。初始时的栈为空。

我们枚举6,因为栈为空,所以6左侧的柱子是哨兵,位置为-1。随后我们将6入栈。

栈:[6(0)]。(这里括号内的数字表示柱子在原数组中的位置)

我们枚举7,由于6<7,因此不会移除栈顶元素,所以7左侧的柱子是6,位置为0。随后我们将7入栈。

栈:[6(0), 7(1)]

我们枚举5,由于 $7\geq 5$ ,因此移除栈顶元素7。同样地, $6 \geq 5$ ,再移除栈顶元素6。此时栈为空,所以5左侧的柱子是哨兵,位置为−1。随后我们将5入栈。

栈:[5(2)]

接下来的枚举过程也大同小异。我们枚举2,移除栈顶元素5,得到2左侧的柱子是哨兵,位置为−1。将 2入栈。

栈:[2(3)]

我们枚举4,5和9,都不会移除任何栈顶元素,得到它们左侧的柱子分别是2,4和5,位置分别为3,4和5。将它们入栈。

栈:[2(3), 4(4), 5(5), 9(6)]

我们枚举3,依次移除栈顶元素9,5和4,得到3左侧的柱子是2,位置为3。将3入栈。

栈:[2(3), 3(7)]

这样以来,我们得到它们左侧的柱子编号分别为[-1, 0, -1, -1, 3, 4, 5, 3]。用相同的方法,我们从右向左进行遍历,也可以得到它们右侧的柱子编号分别为 [2, 2, 3, 8, 7, 7, 7, 8],这里我们将位置8看作哨兵。

在得到了左右两侧的柱子之后,我们就可以计算出每根柱子对应的左右边界,并求出答案了。

分析:单调栈的时间复杂度是多少?直接计算十分困难,但是我们可以发现:每一个位置只会入栈一次(在枚举到它时),并且最多出栈一次。

因此当我们从左向右/总右向左遍历数组时,对栈的操作的次数就为O(N)。所以单调栈的总时间复杂度为O(N)。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left, right = [0] * n, [0] * n

        mono_stack = list()
        for i in range(n):
            while mono_stack and heights[mono_stack[-1]] >= heights[i]:
                mono_stack.pop()
            left[i] = mono_stack[-1] if mono_stack else -1
            mono_stack.append(i)

        mono_stack = list()
        for i in range(n - 1, -1, -1):
            while mono_stack and heights[mono_stack[-1]] >= heights[i]:
                mono_stack.pop()
            right[i] = mono_stack[-1] if mono_stack else n
            mono_stack.append(i)

        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0
        return ans

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。

方法二:单调栈+常数优化

在方法一中,我们首先从左往右对数组进行遍历,借助单调栈求出了每根柱子的左边界,随后从右往左对数组进行遍历,借助单调栈求出了每根柱子的右边界。那么我们是否可以只遍历一次就求出答案呢?

答案是可以的。在方法一中,我们在对位置i进行入栈操作时,确定了它的左边界。从直觉上来说,与之对应的我们在对位置i进行出栈操作时可以确定它的右边界!仔细想一想,这确实是对的。当位置i被弹出栈时,说明此时遍历到的位置 $i_0$ 的高度小于等于 $\textit{height}[i]$ ,并且在 $i_0$ 与i之间没有其他高度小于等于 $\textit{height}[i]$ 的柱子。这是因为,如果在i和 $i_0$ 之间还有其它位置的高度小于等于 $\textit{height}[i]$ 的,那么在遍历到那个位置的时候,i应该已经被弹出栈了。所以位置 $i_0$ 就是位置i的右边界。

等等,我们需要的是一根柱子的左侧且最近的小于其高度的柱子,但这里我们求的是小于等于,那么会造成什么影响呢?答案是:我们确实无法求出正确的右边界,但对最终的答案没有任何影响。这是因为在答案对应的矩形中,如果有若干个柱子的高度都等于矩形的高度,那么最右侧的那根柱子是可以求出正确的右边界的,而我们没有对求出左边界的算法进行任何改动,因此最终的答案还是可以从最右侧的与矩形高度相同的柱子求得的。读者可以仔细思考一下这一步。

在遍历结束后,栈中仍然有一些位置,这些位置对应的右边界就是位置为n的哨兵。我们可以将它们依次出栈并更新右边界,也可以在初始化右边界数组时就将所有的元素的值置为n。

我们沿用方法一中的例子[6, 7, 5, 2, 4, 5, 9, 3],下面的幻灯片给出了优化后的流程。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left, right = [0] * n, [n] * n

        mono_stack = list()
        for i in range(n):
            while mono_stack and heights[mono_stack[-1]] >= heights[i]:
                right[mono_stack[-1]] = i
                mono_stack.pop()
            left[i] = mono_stack[-1] if mono_stack else -1
            mono_stack.append(i)

        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0
        return ans

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。