京公网安备11010502063487号给定一排宽度为 1 的柱子的高度，求柱状图里能勾勒出的最大矩形的面积（矩形必须完全在柱子里面）。一个矩形的高度由它覆盖的柱子里最矮的那根决定，所以对每根柱子 i，以它为最矮柱子的最大矩形，向左向右分别延伸到第一根比它矮的柱子为止。暴力做法是对每个起点向右扩展并维护最小高度，O(n²)。单调栈可以把每根柱子的左右边界一次找出来：栈里保存柱高不减的柱子的下标，遇到更矮的柱子，就说明栈顶那根柱子的右边界找到了，弹出它，弹出之后的栈顶就是它的左边界，立刻算出面积。本文用真实数据展示"末尾没有哨兵"的错误，实测单调栈与暴力的耗时，给出五种语言的实现，并把栈的过程做成分步演示。
完整题目见官方页面（链接在文末）。基准解枚举每个左端点，向右扩展并维护区间内的最小高度，用"最小高度 × 宽度"更新答案，是 O(n²) 的另一种写法。一共 14 组用例，覆盖：官方两个示例、单个柱子、高度为 0、递增、递减、全相同、中间有 0 把柱状图隔开：
输入 [[2,1,5,6,2,3]] 输出 10 输入 [[2,4]] 输出 4 输入 [[1]] 输出 1 输入 [[0]] 输出 0 输入 [[1,1]] 输出 2 输入 [[1,2,3,4,5]] 输出 9
只有遇到更矮的柱子时才弹出结算。如果数组扫描完了，栈里还剩下的柱子（比如整体递增的序列）就没有机会被弹出。常见的处理是在数组末尾追加一根高度 0 的"哨兵"柱子，让所有剩下的柱子都被弹出结算。下面是没有哨兵的写法与 solve 的真实结果：
# 没有末尾哨兵、扫描完没有清空栈的写法 [2, 1, 5, 6, 2, 3]: 没有哨兵 -> 10 solve -> 10 [1, 2, 3, 4, 5]: 没有哨兵 -> 0 solve -> 9 [2, 4]: 没有哨兵 -> 0 solve -> 4 [5, 4, 3, 2, 1]: 没有哨兵 -> 9 solve -> 9 随机 20000 个数组：没有哨兵的写法出错的有 8408 个（42.0%）
[1, 2, 3, 4, 5]（整体递增，没有一根柱子被弹出过）得到 0，正确答案是 9；[2, 4] 得到 0，正确答案是 4。官方示例 [2, 1, 5, 6, 2, 3] 碰巧一致，因为最大矩形在扫描过程中就已经结算了。在随机的 20000 个数组里，没有哨兵的写法出错的有 8408 个，占 42.0%。
栈里存下标，对应的柱高从栈底到栈顶不减。对每个位置 i（i 从 0 到 n，i = n 时当前高度取 0，即哨兵）：只要栈非空并且栈顶的柱高不小于当前高度 h，就弹出栈顶，它的高度是 height；弹出之后，如果栈空，说明左边没有更矮的柱子，左边界是 -1，否则左边界是新的栈顶下标；右边界就是 i（不含），所以宽度是 i - left - 1，面积是 height × 宽度，更新答案。然后把 i 压栈。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(heights): st = [] # 单调栈：存下标，对应的柱高从栈底到栈顶严格不减 best = 0 n = len(heights) for i in range(n + 1): h = heights[i] if i < n else 0 # 在末尾放一根高度 0 的"哨兵"柱子，把栈里剩下的柱子全部弹出结算 while st and heights[st[-1]] >= h: # 当前柱子不比栈顶高：栈顶那根柱子往右最远只能延伸到 i-1 height = heights[st.pop()] left = st[-1] if st else -1 # 弹出之后的栈顶就是往左第一个更矮的柱子（栈空说明左边没有更矮的） best = max(best, height * (i - left - 1)) st.append(i) return best
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,1,5,6,2,3]] → 10 [[2,4]] → 4 [[1]] → 1 [[0]] → 0 [[1,1]] → 2 [[1,2,3,4,5]] → 9
Java · 解法代码class Solution { public int largestRectangleArea(int[] heights) { Deque<Integer> st = new ArrayDeque<>(); // 单调栈：存下标，对应的柱高从栈底到栈顶不减 int best = 0, n = heights.length; for (int i = 0; i <= n; i++) { int h = i < n ? heights[i] : 0; // 在末尾放一根高度 0 的"哨兵"柱子，把栈里剩下的柱子全部弹出结算 while (!st.isEmpty() && heights[st.peek()] >= h) { // 当前柱子不比栈顶高：栈顶那根柱子往右最远只能延伸到 i-1 int height = heights[st.pop()]; int left = st.isEmpty() ? -1 : st.peek(); // 弹出之后的栈顶就是往左第一个更矮的柱子 best = Math.max(best, height * (i - left - 1)); } st.push(i); } return best; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,1,5,6,2,3]] → 10 [[2,4]] → 4 [[1]] → 1 [[0]] → 0 [[1,1]] → 2 [[1,2,3,4,5]] → 9
Go · 解法代码func largestRectangleArea(heights []int) int { st := []int{} // 单调栈：存下标，对应的柱高从栈底到栈顶不减 best, n := 0, len(heights) for i := 0; i <= n; i++ { h := 0 // 在末尾放一根高度 0 的"哨兵"柱子，把栈里剩下的柱子全部弹出结算 if i < n { h = heights[i] } for len(st) > 0 && heights[st[len(st)-1]] >= h { // 当前柱子不比栈顶高：栈顶那根柱子往右最远只能延伸到 i-1 height := heights[st[len(st)-1]] st = st[:len(st)-1] left := -1 // 弹出之后的栈顶就是往左第一个更矮的柱子 if len(st) > 0 { left = st[len(st)-1] } if area := height * (i - left - 1); area > best { best = area } } st = append(st, i) } return best }
$ go build -o bin . && ./bin < cases.jsonl [[2,1,5,6,2,3]] → 10 [[2,4]] → 4 [[1]] → 1 [[0]] → 0 [[1,1]] → 2 [[1,2,3,4,5]] → 9
JavaScript · 解法代码function largestRectangleArea(heights) { const st = []; // 单调栈：存下标，对应的柱高从栈底到栈顶不减 let best = 0; const n = heights.length; for (let i = 0; i <= n; i++) { const h = i < n ? heights[i] : 0; // 在末尾放一根高度 0 的"哨兵"柱子，把栈里剩下的柱子全部弹出结算 while (st.length > 0 && heights[st[st.length - 1]] >= h) { // 当前柱子不比栈顶高：栈顶那根柱子往右最远只能延伸到 i-1 const height = heights[st.pop()]; const left = st.length > 0 ? st[st.length - 1] : -1; // 弹出之后的栈顶就是往左第一个更矮的柱子 best = Math.max(best, height * (i - left - 1)); } st.push(i); } return best; }
$ node run.js < cases.jsonl [[2,1,5,6,2,3]] → 10 [[2,4]] → 4 [[1]] → 1 [[0]] → 0 [[1,1]] → 2 [[1,2,3,4,5]] → 9
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: int largestRectangleArea(vector<int>& heights) { vector<int> st; // 单调栈：存下标，对应的柱高从栈底到栈顶不减 int best = 0, n = heights.size(); for (int i = 0; i <= n; i++) { int h = i < n ? heights[i] : 0; // 在末尾放一根高度 0 的"哨兵"柱子，把栈里剩下的柱子全部弹出结算 while (!st.empty() && heights[st.back()] >= h) { // 当前柱子不比栈顶高：栈顶那根柱子往右最远只能延伸到 i-1 int height = heights[st.back()]; st.pop_back(); int left = st.empty() ? -1 : st.back(); // 弹出之后的栈顶就是往左第一个更矮的柱子 best = max(best, height * (i - left - 1)); } st.push_back(i); } return best; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[2,1,5,6,2,3]] → 10 [[2,4]] → 4 [[1]] → 1 [[0]] → 0 [[1,1]] → 2 [[1,2,3,4,5]] → 9
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
柱子个数 n 分别为 1000、3000、1 万、100 万，每个规模取三次中最快的一次：
柱子个数 n | 暴力解 | 本文解法
1000 | 37.652 ms | 0.138 ms
3000 | 343.572 ms | 0.427 ms
10000 | 3961.437 ms | 1.398 ms
1000000 | （未测，太慢） | 146.960 ms暴力解从 1000 到 3000（3 倍）耗时增长约 9.1 倍，从 3000 到 1 万增长约 11.5 倍，是平方增长；单调栈从 1000 到 1 万（10 倍）增长约 10.1 倍，是线性，100 万根柱子只需要 147.0ms。n = 1 万时暴力解 3961ms，单调栈 1.4ms，约 2800 倍。暴力解在 n = 100 万时没有再测。
Python 版本另外和暴力解做了随机对拍：长度 1 到 12，高度 0 到 8：
随机对拍 30000 组（长度 1 到 12、取值 0 到 8 的随机柱高），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [2, 1, 5, 6, 2, 3]，答案 10（高度 5、宽度 2，覆盖下标 2 和 3）。可以看到：读到高度 1 时，弹出高度 2 的柱子；读到高度 2（下标 4）时，先弹出高度 6（宽 1，面积 6），再弹出高度 5（宽 2，面积 10，刷新最大值）；最后的哨兵柱子把栈里剩下的都弹出结算。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。