LeetCode LCR 039. 柱状图中最大的矩形

约 4 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 栈 LCR 单调栈

题目描述

✅ LCR 039. 柱状图中最大的矩形

image-20260928235632061

image-20260928235632063

题意分析

每根柱子宽度为 $1$，矩形必须覆盖一段连续柱子。对选定区间，矩形高度最多为区间最小柱高，因此面积是“最小高度乘连续宽度”。可以反过来固定矩形高度，寻找它能覆盖的最宽区间。

柱高允许为零，等高柱子可以组成更宽的矩形。零高度会阻断正面积矩形；全零时答案为 $0$。

解法：单调不减栈

核心思路

[!blue]

从左到右扫描，用栈保存尚未结算的柱子下标，栈底到栈顶的高度单调不减。当前高度不低于栈顶时，已有柱子的矩形仍可能向右扩展，暂不结算，直接把当前下标入栈。

当前高度更矮时，栈顶高度 height 已无法扩展到当前位置 i，可以弹出并计算面积。弹出后的栈顶记为 left，空栈时取 -1；从 left + 1 到 i - 1 的柱子都不低于 height，所以本次矩形宽度为 i - left - 1。继续弹栈，直到剩余栈顶不高于当前柱子，再压入当前下标。

代码只在高度严格大于当前值时弹栈，所以 left 的高度可能与弹出柱子相等，本次面积未必是这个高度的最大面积。同一可延伸区间中的等高柱子会从右向左依次结算，最靠左的那根最终越过全部等高位置，覆盖到真正更矮的左边界，因此最大宽度不会遗漏。

任意最优矩形都有一个最低柱高，把它扩展到左右更矮柱子之前只会增大面积；这段最低高度最终会由栈中的某个等高候选完整结算。扫描末尾再处理一个虚拟高度 $0$，即可弹出所有剩余正高度候选；零高度残留不会贡献面积。

解题步骤

  1. 创建下标栈，最大面积初始化为 $0$。
  2. 扫描位置 $0$ 到 $n$；位置 $n$ 的当前高度直接取 $0$，不读取 heights[n]。
  3. 栈顶高度严格大于当前高度时弹出，用新栈顶或 -1 作为 left，计算 height * (i - left - 1)。
  4. 完成所有弹栈后压入当前下标。处理完虚拟位置后结束扫描，返回最大面积。

代码实现

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] stack = new int[heights.length + 1];
        int top = -1;
        int ans = 0;

        for (int i = 0; i <= heights.length; i++) {
            int cur = i == heights.length ? 0 : heights[i];

            while (top >= 0 && heights[stack[top]] > cur) {
                // 弹出的柱子以自身高度为矩形最矮高度，左右边界此时已确定。
                int height = heights[stack[top--]];
                int left = top >= 0 ? stack[top] : -1;

                ans = Math.max(ans, height * (i - left - 1));
            }

            stack[++top] = i;
        }

        return ans;
    }
}

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0)
    ans := 0

    for i := 0; i <= len(heights); i++ {
        cur := 0
        if i < len(heights) {
            cur = heights[i]
        }
        for len(stack) > 0 && heights[stack[len(stack)-1]] > cur {
            // 当前下标是右边界，弹出后的栈顶给出本次左边界。
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            area := height * (i - left - 1)
            if area > ans {
                ans = area
            }
        }
        stack = append(stack, i)
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。每个真实下标入栈一次、至多出栈一次，末尾只多处理一个虚拟位置。
  • 空间复杂度：$O(n)$。栈最多保存 $n+1$ 个下标，其中包含末尾的虚拟位置。

关键点总结

[!green]

  • 更矮柱子确定右边界，弹栈后才能得到本次计算所用的左边界。
  • 严格 > 弹栈允许等高柱子共存，最大宽度由较靠左的同高度候选覆盖。
  • 末尾虚拟高度 $0$ 负责结算仍可向右延伸的正高度矩形。

易错点总结

[!yellow]

  • 宽度为 i - left - 1，左右两个边界位置都不计入本次区间。
  • 不处理末尾虚拟高度，会漏掉直到数组结束都未遇到更矮柱子的候选。
  • 弹栈后的左边界可能等高，不能把每次弹栈都解释为找到左右两个严格更矮的位置。

相似题目

题目 难度 关联与区别
85. 最大矩形 困难 以每一行为底，逐列累计向上连续1的个数作为柱高，遇0清零；再复用本题求柱状图最大矩形，取各行结果的最大值。
42. 接雨水 困难 同样利用高度与边界计算面积，原题求凹槽容水，本题求由最矮柱限制的完整矩形。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/87749836
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！