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

约 5 分钟
文章信息 14 个分类 3 个标签
分类
LeetCode CodeTop 困难 已解决 20-50 LeetCode 热题 100 腾讯 字节 阿里 华为 微软 美团 百度 B站
标签
数组 栈 单调栈

题目描述

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

image-20260928200952039

image-20260928200952040

题意分析

柱状图中每根柱子的宽度都是一，高度为非负整数。选择一段连续柱子，在这些柱子覆盖的区域内画矩形，求能够得到的最大面积。

对固定的一段柱子，矩形高度不能超过其中最矮的柱子，宽度就是连续柱子的数量；矩形可以低于较高柱子的顶端，不需要把选中的每根柱子完整覆盖。问题因此变成：考虑各个可能的最低高度，找到它能延伸的宽度。

解法：单调递增栈

核心思路

[!blue]

任何最优矩形都可以把高度提高到它覆盖区间的最矮柱高，因此按柱高考虑候选不会漏解。向右扫描时，某根柱子还能延伸多远尚未确定，先把它的下标放入栈；直到遇到更低柱子，才知道这一高度不能再跨过当前位置，需要结算面积。

栈中的下标递增，对应高度非递减。当前高度低于栈顶时，弹出该柱，记其高度为 height。当前下标 i 是它右侧第一个严格更低的位置；弹出后的新栈顶记为 left，栈空则取 -1。开区间 (left, i) 内的柱子都不低于 height，所以可以计算候选面积 height * (i - left - 1)。

本实现只在严格更高时弹栈，因此新栈顶可能与被弹柱等高，不一定是严格更低的左边界。此时当前候选没有覆盖整段等高区域，但更靠左的等高柱仍留在栈中；它稍后以相同高度结算时，会获得更宽的区间。最终最靠左的那根能覆盖整个有效范围，最大面积不会遗漏。

当前低柱可能同时截断多个更高柱，所以需要持续弹栈；处理完之后再将当前下标入栈。扫描末尾额外使用一个虚拟零高度，把尚未遇到更低值的正高度柱统一结算。零高度柱即使留在栈中也只能贡献零面积，不影响答案，虚拟位置本身不入栈。

解题步骤

  1. 创建保存柱子下标的空栈，最大面积初始化为零。
  2. 下标从零扫描到 n；正常位置读取原高度，i == n 时使用虚拟零高度。
  3. 只要栈顶柱高严格大于当前高度，就弹出它，保存其高度。
  4. 弹出后读取新栈顶作为左侧界限，栈空用 -1；用 height * (i - left - 1) 更新答案。
  5. 连续弹栈结束后，若仍是实际柱子位置，就将下标入栈。完成末尾结算后返回最大面积。

代码实现

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

        for (int i = 0; i <= n; i++) {
            // 末尾虚拟零触发结算，不需要把哨兵位置入栈。
            int cur = i == n ? 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));
            }

            if (i < n) {
                stack[++top] = i;
            }
        }

        return ans;
    }
}

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0, len(heights))
    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
            }
        }
        if i < len(heights) {
            stack = append(stack, i)
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，每个下标入栈一次、至多弹出一次，全部内层循环的操作总数不超过线性规模。
  • 空间复杂度：$O(n)$，高度一直不下降时，栈可能保存全部柱子的下标。

关键点总结

[!green]

  • 栈保存还未确定右侧阻挡位置的候选高度及其下标。
  • 结算时先弹出当前候选，再读取左侧界限，宽度来自两个界限之间的位置数。
  • 严格弹栈允许等高柱共存，完整等高范围最终由更靠左的候选覆盖。
  • 虚拟零统一处理末尾残留的正高度候选，无需复制或扩展输入数组。

易错点总结

[!yellow]

  • 用 i - left 计算宽度，把不属于当前候选矩形的界限也算进去，面积会多一列。
  • 在弹栈之前读取 left，拿到的是当前候选自身，不能表示它左边尚保留的位置。
  • 忘记末尾结算，一直上升的柱子不会在正常扫描中弹出，最大面积就可能完全没计算。
  • 栈空时令左界为零，会漏掉可以覆盖第零根柱子的矩形；虚拟左界应为 -1。
  • 把新栈顶总说成严格更低的柱子，与当前严格 > 弹栈的等高处理不一致。
  • 栈只存高度、不存下标，无法根据位置计算连续宽度。

相似题目

题目 难度 关联与区别
85. 最大矩形 困难 以每一行为底，逐列累计向上连续1的个数作为柱高，遇0清零；再复用本题求柱状图最大矩形，取各行结果的最大值。
42. 接雨水 困难 同样利用高度与边界计算面积，原题求凹槽容水，本题求由最矮柱限制的完整矩形。
907. 子数组的最小值之和 中等 用单调栈确定元素能影响的连续区间边界；本题以每根柱高计算最大矩形面积，该题统计每个值作为区间最小值的贡献。
补充题 186. 数组两侧最近严格较小元素的位置 中等 抽出单调栈子问题，返回两侧最近严格更小的位置，不计算矩形面积。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/76548018
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！