城市天际线里的最大广告牌

不是找最高柱子，而是找「某根柱子作为最低高度时能撑开的最大宽度」

heights=[2,1,5,6,2,3]

答案 10

单调栈时间 O(n)空间 O(n)

弹栈公式

height = heights[top]
rightLess = i
leftLess = stackTopAfterPop（栈空则 −1）
width = rightLess − leftLess − 1
area = height × width

Step 1/17题目

城市天际线 · 柱状图

maxArea = 0

Step 1：题目 — 城市天际线最大广告牌

一排高楼 heights=[2,1,5,6,2,3] 代表城市天际线。要在连续楼体上贴一块矩形广告牌，面积 = 高度 × 宽度。目标：找出最大面积。

不是找最高楼，而是找「某根柱子作为最低高度时能撑开的最大宽度」。

为什么正确

矩形高度必须由区间内最矮柱决定；每根柱都可能是那块矩形的「地板高度」。

不变量

尚未开始扫描；最大面积候选 maxArea = 0。

单调递增栈

栈底 → 栈顶，高度严格递增

stack = []

栈里放的不是已经算完的柱子，而是还在等待右边第一个更矮柱子的柱子。

Go 代码同步

1func largestRectangleArea(heights []int) int {
2    heights = append(heights, 0)
3    stack := []int{}
4    maxArea := 0
5 
6    for i, h := range heights {
7        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
8            top := stack[len(stack)-1]
9            stack = stack[:len(stack)-1]
10 
11            height := heights[top]
12 
13            leftLess := -1
14            if len(stack) > 0 {
15                leftLess = stack[len(stack)-1]
16            }
17 
18            width := i - leftLess - 1
19            area := height * width
20            if area > maxArea {
21                maxArea = area
22            }
23        }
24 
25        stack = append(stack, i)
26    }
27 
28    return maxArea
29}

Go 代码逐行要点

append 0：哨兵，统一清算。
stack 存下标，不存高度，因为要计算宽度。
while 当前柱子更矮：说明栈顶右边界出现。
top 是当前被结算的柱子。
leftLess 是弹栈后的新栈顶。
width = i - leftLess - 1。
每根柱子最多入栈一次、出栈一次，所以 O(n)。

复杂度（必须记对）

时间 O(n): 每根柱子最多入栈一次、出栈一次。
空间 O(n): 单调栈最坏存 n 个下标。

常见误区

误区 1：最大矩形一定包含最高柱
最高柱宽度可能只有 1，面积 = 高×1 不一定最大。例：高 6 宽 1 = 6，高 5 宽 2 = 10。
误区 2：宽度 = 弹出了几个柱子
宽度由左右第一个更矮柱子的下标差决定：width = rightLess - leftLess - 1，不是 pop 次数。
误区 3：栈里存高度即可
必须存 index，否则无法计算 leftLess/rightLess 之间的宽度。
误区 4：遍历完就结束
栈里可能还有没找到右边界的柱子，需要 append 0 哨兵或遍历后统一清算。
误区 5：空间 O(1)
单调栈最坏存 n 个下标，空间复杂度是 O(n)，不是 O(1)。

面试怎么说

柱状图最大矩形：矩形高度一定来自某一根柱子。以第 k 根为高时，左右扩张到第一个更矮柱，即 leftLess/rightLess。用单调递增栈存「还在等右边更矮柱」的下标；扫描到更矮的 h 时，栈顶的 rightLess 就是当前 i，弹出后新栈顶是 leftLess，width = i - leftLess - 1，更新 maxArea。末尾 append 0 当哨兵强制清空栈。每柱最多入栈出栈各一次，时间 O(n)，栈最坏 O(n) 空间。

迁移练习

LC85 最大矩形 — 每行转 histogram 再调 LC84
LC42 接雨水 — 理解「左右第一个更矮/更高」的栈思维
LC739 每日温度 — 单调栈找下一个更小/更大