柱状图中最大的矩形

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

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

示例 1：

 输入：heights = [2,1,5,6,2,3]
 输出：10
 解释：最大的矩形由高度为 5 和 6 的两个柱子组成，宽度为 2，面积为 10。

示例 2：

 输入：heights = [2,4]
 输出：4

提示：

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

单调递增栈：

 class Solution {
 public:
     int largestRectangleArea(vector<int>& heights) {
         int n = heights.size();
         int ans = 0;
         stack<int> st;
         st.push(-1);
 ​
         for (int i = 0; i <= n; ++i)
        {
             int currentHeight = (i == n ? 0 : heights[i]);
 ​
             while (st.top() != -1 && heights[st.top()] >= currentHeight)
            {
                 int height = heights[st.top()];
                 st.pop();
 ​
                 int width = i - st.top() - 1;
                 ans = max(ans, height * width);
            }
 ​
             st.push(i);
        }
 ​
         return ans;
    }
 };

核心思想

一个矩形的面积由三部分决定：

矩形面积 = 矩形高度 * 矩形宽度

如果固定某一根柱子作为矩形的最低高度，那么还需要找到：

• 它向左最远能延伸到哪里
• 它向右最远能延伸到哪里

直接对每根柱子向左右查找边界，最坏时间复杂度是 O(n^2)。

这题的关键是使用单调栈维护这些还没有确定右边界的柱子。

从左到右扫描时，栈中保存的柱子高度保持单调递增。

当遇到一个更矮或等高的柱子时，说明栈顶柱子的右边界已经确定：

当前柱子是栈顶柱子右侧第一个高度不高于它的柱子。

被弹出的柱子左边界，则由弹栈后新的栈顶确定。

于是可以在弹栈时直接计算以该柱子高度为高的最大矩形面积。

栈中存什么

栈中保存的是柱子的下标，而不是高度：

 stack<int> st;

保存下标有两个原因：

1. 可以通过下标访问柱子高度 heights[index]。
2. 可以根据下标计算矩形宽度。

栈中下标对应的柱子高度保持严格递增：

 heights[st[0]] < heights[st[1]] < ... < heights[st.top()]

代码先压入一个下标 -1 作为左边界哨兵。

它不对应真实柱子，只表示所有柱子左侧的边界。

这样即使弹出栈中最后一个真实柱子，也可以用：

i - (-1) - 1

计算从下标 0 开始的矩形宽度，不需要额外判断栈是否为空。

为什么遇到更矮柱子时可以弹栈

假设当前扫描到下标 i，栈顶下标为 top，并且：

heights[i] <= heights[top]

说明当前柱子不高于栈顶柱子。

由于数组是从左到右扫描的，所以 i 是栈顶柱子右侧第一个不高于它的柱子。

栈顶柱子无法继续向右延伸到 i，因此它的右边界已经确定，可以弹出并计算面积。

弹出 top 后，新的栈顶是 top 左侧最近的、比当前柱子更矮的柱子。

所以以被弹出柱子为高度的最大矩形，其左右边界是：

• 左边界：新的栈顶下标加 1
• 右边界：当前下标减 1

矩形宽度就是：

i - st.top() - 1

为什么宽度是 i - st.top() - 1

假设弹出下标 j 后，新的栈顶下标是 left，当前下标是 i。

由于单调栈性质：

• left 对应的高度小于 heights[j]
• i 对应的高度也小于或等于 heights[j]
• left 和 i 之间的柱子高度都不小于 heights[j]

因此，矩形可以覆盖的下标范围是：

[left + 1, i - 1]

宽度为：

(i - 1) - (left + 1) + 1 = i - left - 1

代码中的 left 就是弹栈后的 st.top()，所以写成：

width = i - st.top() - 1

为什么要在末尾补一个高度为 0 的柱子

如果数组扫描结束时，栈中还剩柱子，说明这些柱子右侧一直没有遇到更矮的柱子。

但它们对应的最大矩形仍然需要计算。

例如：

 heights = [2,4]

扫描真实柱子后，柱子 2 和 4 仍可能在栈中。

在数组末尾假想一个高度为 0 的柱子，就可以把所有剩余柱子依次弹出并结算。

代码通过：

 for (int i = 0; i <= n; ++i)

以及：

 int currentHeight = (i == n ? 0 : heights[i]);

实现这个哨兵柱子。

为什么相同高度也可以弹出

代码使用：

 heights[st.top()] >= currentHeight

作为弹栈条件。

遇到相同高度时，先入栈的柱子会被弹出。

这样可以让后面保留的相同高度柱子拥有更靠左的有效边界，最终仍然能够覆盖相同高度可以覆盖的全部范围。

例如：

 heights = [2,2,2]

扫描到最后的高度 0 时，三个高度为 2 的柱子会依次弹出，最终会计算出高度 2、宽度 3 的矩形，面积为 6。

因此使用 >= 不会漏掉相同高度组成的最大矩形。

边界情况

如果只有一根柱子，例如：

 heights = [5]

末尾的高度 0 会弹出它，宽度为 1，面积为 5。

如果数组中的柱子高度严格递增，真实扫描结束时很多柱子仍在栈中，末尾哨兵会统一结算它们。

如果数组中的柱子高度严格递减，每遇到新柱子都会弹出前面的更高柱子，并及时计算面积。

如果存在高度为 0 的柱子，它相当于把柱状图分成多个独立区域，单调栈会自动利用它作为边界。

如果最大矩形跨越多个柱子，那么每根柱子在弹栈时都会尝试以自身高度作为矩形高度，最大面积不会被遗漏。

正确性证明

我们证明：算法返回的 ans 等于柱状图中所有可构成矩形的最大面积。

结论 1：栈中下标对应的高度始终严格递增

初始时栈中只有哨兵下标 -1，没有对应的真实高度。

处理新柱子时，算法会先弹出所有满足：

heights[st.top()] >= currentHeight

的下标。

弹栈结束后，如果栈顶不是哨兵，则有：

heights[st.top()] < currentHeight

然后把当前下标压入栈中。

因此压入后，栈中真实下标对应的高度仍然严格递增。

结论 2：被弹出的柱子的右边界已经确定

设下标 j 在处理当前下标 i 时被弹出。

弹出条件说明：

heights[i] <= heights[j]

所以 i 是从左到右扫描过程中，第一个位于 j 右侧且高度不高于 heights[j] 的柱子。

因此，以 heights[j] 为矩形高度的矩形不能延伸到 i，它的最右位置只能是 i - 1。

所以 i 正确确定了下标 j 的右边界。

结论 3：被弹出柱子的左边界由新的栈顶确定

弹出下标 j 后，新的栈顶是 j 左侧最近的、尚未被弹出的柱子。

根据栈的严格递增性质，新的栈顶高度小于 heights[j]。

而新的栈顶与 i 之间的柱子，都没有在此前被弹出，说明它们的高度都不小于 heights[j]。

因此，j 能够向左延伸到新的栈顶右侧，不能越过新的栈顶。

所以它的最左位置是：

st.top() + 1

结论 4：每次弹栈计算的面积是该柱子作为最低高度时的最大面积

由结论 2 可知，当前下标 i 是被弹出柱子的右侧第一个不高于它的位置。

由结论 3 可知，弹栈后的新栈顶是被弹出柱子左侧第一个低于它的位置。

所以被弹出柱子能够覆盖的最大连续区间是：

[st.top() + 1, i - 1]

宽度为：

i - st.top() - 1

高度为 heights[j]，因此算法计算出的面积：

heights[j] * (i - st.top() - 1)

正好是以该柱子为最低高度时能够得到的最大矩形面积。

结论 5：所有可能的最大矩形都会被考虑

任意一个矩形都有一个最低高度，可以选择其中一根达到该最低高度的柱子作为代表。

当这根柱子遇到右侧第一个不高于它的柱子时，它会被弹出，并计算能够覆盖的最大区间。

如果它直到真实数组结束都没有遇到更矮柱子，那么末尾补充的高度 0 会将它弹出并计算。

因此，任意可能的最大矩形都会在某个柱子弹出时被计算或被一个不小于它的矩形覆盖。

算法取所有计算面积中的最大值，所以不会漏掉全局最优解。

得出结论

由结论 1 可知，单调栈的结构始终正确。

由结论 2 和结论 3 可知，每个柱子的左右边界都能被正确确定。

由结论 4 可知，每次弹栈计算的面积都是对应柱子的最大合法矩形面积。

由结论 5 可知，所有可能的最大矩形都会被考虑。

因此算法返回的 ans 就是柱状图中最大的矩形面积。

举例理解

以：

 heights = [2,1,5,6,2,3]

为例。

扫描过程如下：

其中下标 2 的柱子高度为 5，弹出时左边界是下标 2 自己左侧的下一个位置 2，右边界是下标 3，所以宽度为 2。

得到面积：

5 * 2 = 10

最终最大面积为：

 10

复杂度分析

每个柱子最多入栈一次、出栈一次。

虽然代码中有嵌套的 while，但所有弹栈操作总次数不超过 n 次。

因此时间复杂度是：

O(n)

答案数组之外，单调栈最坏情况下会保存所有柱子的下标。

所以空间复杂度是：

O(n)