柱状图中最大的矩形 图解题解

柱状图最大矩形在问什么

给出每根柱子的高度 heights，矩形可以横跨相邻的多根柱子，但高度受这一段里最矮那根的限制，求能框出的最大面积。直接枚举「哪一段」有 O(n²) 个区间，每段还要找最矮柱，暴力很贵。换一个枚举对象豁然开朗：最大矩形的上边一定顶着某根柱子的头（否则还能整体升高），所以只需枚举「以哪根柱子为高」，问题变成：每根柱子向左右各能扩到多远。

为什么这题会想到单调栈

柱 i 能扩的范围有清晰的刻画：右边界是右侧第一根比它矮的柱，左边界是左侧第一根比它矮的柱——矮柱像墙一样挡住去路，宽度就是两堵墙之间的格数。对每根柱各自向两边扫是 O(n²)，而「找左右第一个更矮元素」正是单调栈的看家本领。

具体想法是：从左到右扫，维护一个柱高从底到顶递增的栈。只要当前柱不比栈顶矮就入栈；一旦当前柱更矮，就意味着栈顶柱的右墙出现了——它再也扩不过去，此刻信息齐全，立刻弹出结算它的矩形。

弹出瞬间左右边界为什么都是现成的

设弹出的柱子是 top，当前扫到下标 i。右墙显然是 i：它是右侧第一根更矮的柱。左墙则是弹出 top 之后露出的新栈顶：递增栈保证新栈顶比 top 矮，而 top 与新栈顶之间的柱子都已在更早的回合被弹掉，说明它们全都不比 top 矮、挡不住它。所以新栈顶正是左侧第一根更矮的柱。

于是宽度 = i - left - 1，面积 = heights[top] × 宽度。注意宽不是 i - left：左右两堵墙本身都是扩不进去的位置，各要让出一格。栈弹空时 left 取 -1，表示这根柱子一路矮到底，能扩到最左端。

末尾为什么要补一根高度 0 的哨兵

扫描到末尾时，栈里可能还留着一串递增的柱子——它们右侧始终没出现更矮的柱，从未被触发结算。参考代码在 heights 末尾追加一根高 0 的哨兵柱，它比任何真实柱都矮，会把栈里剩余的柱子逐一逼出来算完。忘加哨兵是这题最常见的漏答来源。以输入 [2,1,5,6,2,3] 为例：最优解是以柱 2 为高、罩住柱 2 和柱 3 的矩形，高 5 宽 2 面积 10，它由下标 4 的矮柱触发结算；而末尾的柱 4、柱 5 右侧再没有更矮的柱，若无哨兵就永远不会被结算。

复杂度与相关题的关系

时间 O(n)：每根柱子入栈一次、出栈一次，总操作线性。空间 O(n)：最坏整体递增，栈装下全部下标。栈里必须存下标而非高度，因为宽度要用下标差来算。

这套「找左右第一根更矮柱」的框架是一类题的内核：LeetCode 85 最大矩形就是把 0/1 矩阵逐行压成柱状图后，每行调用本题解法取最大值。把 84 吃透，85 只剩一步转化。

Python

def largestRectangleArea(heights):
    heights = heights + [0]      # 末尾哨兵，逼出栈中剩余柱
    st, best = [], 0             # st 存下标，柱高递增
    for i, h in enumerate(heights):
        while st and h < heights[st[-1]]:
            top = st.pop()
            left = st[-1] if st else -1
            width = i - left - 1
            best = max(best, heights[top] * width)
        st.append(i)
    return best

C++

int largestRectangleArea(vector<int>& heights){
    heights.push_back(0);        // 末尾哨兵
    stack<int> st; int best = 0;  // 存下标，柱高递增
    for(int i = 0; i < (int)heights.size(); i++){
        while(!st.empty() && heights[i] < heights[st.top()]){
            int top = st.top(); st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            best = max(best, heights[top] * width);
        }
        st.push(i);
    }
    return best;
}

Java

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] h = new int[n + 1];                 // 末尾哨兵 0
    System.arraycopy(heights, 0, h, 0, n);
    Deque<Integer> st = new ArrayDeque<>();   // 存下标，柱高递增
    int best = 0;
    for (int i = 0; i <= n; i++) {
        while (!st.isEmpty() && h[i] < h[st.peek()]) {
            int top = st.pop();
            int left = st.isEmpty() ? -1 : st.peek();
            int width = i - left - 1;
            best = Math.max(best, h[top] * width);
        }
        st.push(i);
    }
    return best;
}