柱状图中最大的矩形：单调栈消除「悬崖」的工程思维

老张2026/4/30大约 10 分钟

柱状图中最大的矩形：单调栈消除「悬崖」的工程思维

适读人群：Java 开发者、冲击大厂算法面试的工程师 | 阅读时长：约22分钟 | 难度：Hard

开篇故事

我在某电商公司做了三年基础架构，有一段时间在做报表系统的可视化模块。有个需求：在柱状图上自动高亮"面积最大的矩形区域"，用来做业绩达标率的可视化展示。当时的前端实现是暴力枚举，数据点多了之后渲染卡得要死，帧率掉到个位数。

我翻了一下代码，一看就是 O(n²) 甚至 O(n³) 的暴力。我说这个有 O(n) 的解法，用单调栈。前端同学表示没听说过，我花了一个下午把算法讲清楚、改了代码，页面渲染从卡死变成了流畅。

后来这段经历成了我面试候选人时会提到的一个案例——算法不只是刷题，它在工程里真的有用。

LeetCode 84 柱状图中最大的矩形，是我认为单调栈最典型的应用之一。接雨水（LeetCode 42）是找凹槽，这道题是找凸起，两者是镜像问题，用的却是同一个工具。

一、题目解析

LeetCode 84. 柱状图中最大的矩形（Largest Rectangle in Histogram）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入输出示例：

示例 1（经典情况）：

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大矩形是由下标 2,3 两根柱子组成的高度为 5 的矩形，面积 = 5×2 = 10

示例 2（只有一根柱子）：

输入：heights = [2,4]
输出：4

边界情况 3（单调递增）：

输入：heights = [1,2,3,4,5]
输出：9
解释：最大矩形是 [3,4,5] 三根柱子，高度 3，面积 = 3×3 = 9

边界情况 4（全相同高度）：

输入：heights = [3,3,3,3]
输出：12

边界情况 5（单根柱子很高）：

输入：heights = [1,1,1,1,100]
输出：5
解释：全部 5 根柱子高度 1 的矩形面积 5，单独高度 100 的矩形面积也是 100，但 5 < 100

考察的核心知识点：

枚举每根柱子作为矩形最矮柱
找每根柱子左右第一个比它矮的位置
单调栈高效解决"左/右第一个更小元素"问题

二、解法一：暴力解法

思路分析

关键洞察：最大矩形的高度必然等于某根柱子的高度（因为矩形高度是所有柱子中最矮的，所以它等于其中某根柱子的高度）。因此枚举每根柱子作为矩形的高度，找以该高度为基础能延伸的最大宽度。

对于柱子 i（高度 h = heights[i] ），矩形可以向左延伸直到遇到高度小于 h 的柱子，向右也一样。宽度 = 左边界到右边界的距离，面积 = h × 宽度。

暴力：对每根柱子，向左向右各扫描，找到边界。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            int h = heights[i];
            // 向左找第一个高度 < h 的位置
            int left = i;
            while (left > 0 && heights[left - 1] >= h) {
                left--;
            }
            // 向右找第一个高度 < h 的位置
            int right = i;
            while (right < n - 1 && heights[right + 1] >= h) {
                right++;
            }
            
            int width = right - left + 1;
            maxArea = Math.max(maxArea, h * width);
        }
        
        return maxArea;
    }
}

时间复杂度：O(n²)，每根柱子最坏需要向两侧各扫描 O(n)。

空间复杂度：O(1)。

三、解法二：预计算左右边界数组

优化思路

暴力对每根柱子都重新扫描，有大量重复。可以分别预计算每根柱子的"左边界"和"右边界"，再一次性计算所有面积。

用单调栈来计算每根柱子左边第一个比它矮的位置（Left Smaller）和右边第一个比它矮的位置（Right Smaller）。这是单调栈的经典应用之一。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] leftSmaller = new int[n];   // 左边第一个更矮柱子的下标
        int[] rightSmaller = new int[n];  // 右边第一个更矮柱子的下标
        
        // 用单调栈计算 leftSmaller
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        // 用单调栈计算 rightSmaller
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            rightSmaller[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        // 计算每根柱子为最矮柱时的最大面积
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = rightSmaller[i] - leftSmaller[i] - 1;
            maxArea = Math.max(maxArea, heights[i] * width);
        }
        
        return maxArea;
    }
}

时间复杂度：O(n)，每个元素入栈出栈各一次。

空间复杂度：O(n)，两个边界数组加栈。

四、解法三：单调栈一次遍历（工业级最优解）

核心洞见

上面两个栈的预计算版本虽然正确，但需要两次遍历。能否一次遍历就完成所有计算？

核心思路：维护一个单调递增栈（栈中元素高度从栈底到栈顶递增）。当遇到一个高度比栈顶矮的柱子时，说明找到了栈顶柱子的右边界。此时弹出栈顶，计算以栈顶为高度的矩形面积：

左边界：弹出后的新栈顶（因为单调栈保证了新栈顶是左边第一个更矮的）
右边界：当前遍历到的位置 i
宽度 = 右边界 - 左边界 - 1

为了处理"右边没有更矮柱子"的情况（单调递增序列末尾），在数组末尾添加一个高度为 0 的哨兵，强制弹出所有剩余元素。同样，在数组开头添加高度为 0 的哨兵，避免栈空时的边界判断。

完整 Java 代码

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        
        // 添加哨兵：头部和尾部各加一个高度为 0 的虚拟柱子
        // 头部哨兵：保证栈永远不为空，避免空栈判断
        // 尾部哨兵：强制把所有剩余元素从栈中弹出并计算
        int[] h = new int[n + 2];
        h[0] = 0;          // 头部哨兵
        h[n + 1] = 0;      // 尾部哨兵
        for (int i = 0; i < n; i++) h[i + 1] = heights[i];
        
        // 单调递增栈，存下标（对应增加哨兵后的新数组）
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        
        for (int i = 0; i < h.length; i++) {
            // 遇到比栈顶矮的柱子，弹出并计算面积
            while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
                int top = stack.pop();         // 被弹出的柱子（矩形高度）
                int leftBound = stack.peek();  // 左边界（弹出后的新栈顶）
                int width = i - leftBound - 1; // 矩形宽度
                maxArea = Math.max(maxArea, h[top] * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

复杂度分析

时间复杂度：O(n)

每个元素（包括哨兵）最多入栈一次、出栈一次，总操作次数 = 2(n+2)，即 O(n)。

空间复杂度：O(n)

辅助数组 h 是 O(n)，栈最坏情况下存所有元素（单调递增序列），也是 O(n)。

我在 LeetCode 上提交这个方案，运行时间 9ms，击败 96.1% 的 Java 用户。

不使用哨兵的版本（更通用但代码稍复杂）：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        
        for (int i = 0; i <= n; i++) {
            // i == n 时用虚拟高度 0 作为哨兵触发最终清栈
            int curHeight = (i == n) ? 0 : heights[i];
            
            while (!stack.isEmpty() && heights[stack.peek()] > curHeight) {
                int h = heights[stack.pop()];
                // 左边界：栈空时是 -1（表示左边没有更小的，宽度从 0 开始）
                int leftBound = stack.isEmpty() ? -1 : stack.peek();
                int width = i - leftBound - 1;
                maxArea = Math.max(maxArea, h * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}