LeetCode 84. 柱状图中最大的矩形

◎

本节目标

在柱子出栈时确定其左右第一个更矮边界，并计算最大矩形面积。

查看 LeetCode 原题

题意与边界

每根柱宽度为 1，求连续柱子能够围成的最大矩形面积。高度可以为 0；算法只读取输入数组，末尾清栈使用逻辑上的零高度而不永久追加元素。

高度的最大延伸区间

栈保存高度单调不减的柱子下标。遇到更矮高度时，当前下标是被弹出柱子的右侧第一个严格更矮位置；弹出后的新栈顶是该柱不能越过的左侧边界下标，可能与它同高，因此宽度为 i - left - 1。严格 > 让同高柱保留在栈中，最左侧同高柱会在最终结算时代表这一高度的最大宽度。扫描末尾再处理一个虚拟零高度，让所有剩余柱子完成结算。

正确性依据

柱子因更矮的当前高度出栈时，其右边界已经确定；新栈顶给出不可越过的左边界，因此可以结算该柱对应的候选矩形。右侧同高柱可能先以较窄范围结算，但左侧同高柱仍保留更早的左边界，最终覆盖这一高度的最大宽度。所有柱子最终都因更矮柱或虚拟零高度而结算，最大值因此覆盖全局最优矩形。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> pending;
        int answer = 0;
        int n = static_cast<int>(heights.size());
        for (int i = 0; i <= n; i++) {
            int height = i == n ? 0 : heights[i];
            while (!pending.empty() && heights[pending.back()] > height) {
                int index = pending.back();
                pending.pop_back();
                int left = pending.empty() ? -1 : pending.back();
                int width = i - left - 1;
                answer = max(answer, heights[index] * width);
            }
            pending.push_back(i);
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        pending = []
        answer = 0
        n = len(heights)
        for i in range(n + 1):
            height = 0 if i == n else heights[i]
            while pending and heights[pending[-1]] > height:
                index = pending.pop()
                left = -1 if not pending else pending[-1]
                width = i - left - 1
                answer = max(answer, heights[index] * width)
            pending.append(i)
        return answer

复杂度分析

• 时间复杂度：O(n)，每个下标至多入栈和出栈一次。
• 空间复杂度：O(n)。

易错点

• 弹出下标用于取矩形高度；弹栈后的新栈顶用于确定左边界，空栈时左边界为 -1。
• 忘记末尾清栈，遗漏一直单调递增的柱子。
• 直接向输入数组追加哨兵却不恢复，产生隐藏副作用。

模式迁移

当一个元素的答案取决于左右两侧第一个破坏单调性的边界时，可以在出栈瞬间同时确定两侧范围。接雨水、子数组最小值之和也使用类似边界结算。