柱状图中最大的矩形

题意

给定柱状图的高度数组，求能勾勒出的最大矩形面积。

思路

单调栈保存柱子下标，栈底到栈顶高度递增。弹出时，弹出的高度 h 就是被结算柱子的高度，左边界是弹出后新栈顶（第一个更矮的柱），右边界是当前扫描位置 i（第一个右边更矮的柱），宽度 = i - l - 1。

末尾补一个虚拟的 0 高度柱，确保所有栈中剩余柱子都被结算。

代码

cpp

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
27
28
29
30
31
32
33
34#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().largestRectangleArea(a) << '\n';
    return 0;
}

python

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
27#!/usr/bin/env python3
from typing import List


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        st = []
        ans = 0
        for i, h in enumerate(heights):
            while st and heights[st[-1]] > h:
                hh = heights[st.pop()]
                l = st[-1] if st else -1
                ans = max(ans, hh * (i - l - 1))
            st.append(i)
        heights.pop()
        return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().largestRectangleArea(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n)$ ，每个柱子最多入栈出栈一次。
空间复杂度： $O(n)$ ，栈最多存所有下标。

总结

柱状图最大矩形是单调栈的经典应用：弹出时左右第一个更矮的位置决定宽度。末尾补 0 是关键技巧，确保结算所有柱子。

柱状图中最大的矩形

目录

题意

思路

代码

复杂度

总结