直方图中的最大矩形
使用单调栈跟踪左边界，并在一次遍历中计算能够容纳于直方图中的最大矩形面积。
直方图中的最大矩形 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
问题：柱状图中的最大矩形
柱状图中的最大矩形问题（LeetCode 84）给出一个由非负整数组成的数组，表示柱状图中各柱条的高度，每个柱条的宽度为 1。请找出柱状图中能够形成的最大矩形面积。矩形必须覆盖连续的柱条，其高度受所覆盖柱条中最矮柱条的限制。
暴力方法是：对于每一对 (i, j)，计算 [i, j] 中的最小高度，再乘以 (j - i + 1)。这种方法的复杂度为 O(n³)，即使预先计算最小值也需要 O(n²)，仍然太慢。单调栈解法的复杂度为 O(n)。
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
n = len(heights)
max_area = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_area
print('Brute force answer:', brute_force(heights)) # 10关键思路：什么限制了每个柱条的矩形？
对于高度为 h 的每个柱条 i，它作为最小高度时所能形成的最大矩形，会向左延伸到第一个高度小于 h 的柱条，并向右延伸到第一个高度小于 h 的柱条。宽度为 right_boundary - left_boundary - 1，面积为 h × width。
这让问题换了一种表达方式：对于每个柱条，找到它的前一个更小元素（PSE）和下一个更小元素（NSE）。这正是单调递增栈所计算的内容。当我们 pop 柱条 i（因为找到了更矮的柱条）时，当前柱条就是它的 NSE，而 pop 后的新栈顶就是它的 PSE。
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)使用单调栈的一次遍历解法
上面的两次遍历方法虽然可行，但可以合并为一次遍历。使用单调递增栈从左到右处理柱条。当柱条 i 短于栈顶时，pop 栈顶——被弹出柱条的高度就是一个矩形的高度，其右边界是 i，左边界是新的栈顶 + 1。
一个常用技巧是在 heights 末尾 append 一个哨兵值 0。这样，即使自然遍历过程中没有出现更矮的柱条，也能确保最后将所有柱条从栈中弹出。如果没有这个哨兵值，就需要在循环结束后额外清理栈中剩余的元素。
def largest_rectangle(heights):
stack = [] # monotonic increasing: indices of bars
max_area = 0
heights = heights + [0] # sentinel: forces all bars to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # height of the rectangle
width = i if not stack else i - stack[-1] - 1 # left boundary
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
print(largest_rectangle([2, 4])) # 4
print(largest_rectangle([1, 1])) # 2
print(largest_rectangle([0, 9])) # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3])) # 16追踪一次遍历算法
让我们逐步追踪 [2, 1, 5, 6, 2, 3, 0]（包含哨兵值）：
- i=0，h=2：推入 0。栈：[0]
- i=1，h=1：pop 0（h=2，宽度=1，面积=2）。栈为空，推入 1。栈：[1]
- i=2，h=5：5>1，推入 2。栈：[1,2]
- i=3，h=6：6>5，推入 3。栈：[1,2,3]
- i=4，h=2：pop 3（h=6，宽度=4-2-1=1，面积=6），pop 2（h=5，宽度=4-1-1=2，面积=10★），2>1，停止。推入 4。栈：[1,4]
- i=5，h=3：3>2，推入 5。栈：[1,4,5]
- i=6，哨兵 h=0：pop 全部元素，计算面积……
def largest_rectangle_trace(heights):
stack = []
max_area = 0
hs = heights + [0]
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = hs[top] * w
print(f' Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
if area > max_area:
max_area = area
print(' *** NEW MAX ***', end='')
print()
print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
stack.append(i)
print(f'Max area: {max_area}')
return max_area
largest_rectangle_trace([2, 1, 5, 6, 2, 3])宽度计算：为什么是 i - stack[-1] - 1？
当我们从栈中 pop 柱条 j 时，可以确定：j 的矩形右边界是 i（右侧第一个比 j 矮的柱条）。左边界是 pop 后栈中紧挨着 j 下方的柱条，将其记为 k。因此，宽度为 i - k - 1（即从 k+1 到 i-1 的所有柱条）。
如果 pop 后栈为空，j 的矩形会一直延伸到左边界。此时宽度就是 i（索引 0 到 i-1，这些柱条的高度都至少与 heights[j] 一样高）。特殊情况可写为 width = i if not stack else i - stack[-1] - 1。
# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
# stack after pop = [0, 1] => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
# stack after pop = [0] => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.
def compute_boundaries(heights):
hs = heights + [0]
stack = []
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
if stack:
left = stack[-1] + 1
width = i - stack[-1] - 1
else:
left = 0
width = i
print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
stack.append(i)
compute_boundaries([2, 1, 5, 6, 2, 3])二进制矩阵中的最大矩形
最大矩形（LeetCode 85）将柱状图问题扩展到了二维二进制矩阵。对于每一行，计算每个单元格上方连续 1 的高度。这会为该行创建一个柱状图。对每一行的柱状图应用柱状图中最大矩形的算法。所有行中的最大值就是答案。
这样就能将二维问题转化为 n 个重复的一维柱状图问题。对于一个有 m 行、n 列的矩阵，时间复杂度为 O(m × n)：每行执行一次柱状图遍历，每次遍历的复杂度为 O(n)。
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
def hist_max_area(h):
stack, area = [], 0
for i, hh in enumerate(h + [0]):
while stack and h[stack[-1]] > hh:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = max(area, h[top] * w)
stack.append(i)
return area
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, hist_max_area(heights[:]))
return max_area
matrix = [['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']]
print(maximal_rectangle(matrix)) # 6柱状图问题中的边界情况
需要处理的重要边界情况：
- 所有柱条高度相同：整个数组构成一个矩形；答案 = n × 高度
- 单调递增：直到哨兵值出现前都不会发生 pop；最后一个柱条的面积最大
- 只有一个柱条：答案 = height[0]
- 高度为 0 的柱条：它们充当自然哨兵值，将柱状图分割为彼此独立的片段
在末尾追加 0 这一哨兵值，可以通过强制在末尾 pop 所有剩余柱条来处理单调递增的情况。如果没有它，就需要在主迭代之后使用单独的清理循环。
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * w)
stack.append(i)
return max_area
# Edge cases
print(largest_rectangle([5, 5, 5, 5])) # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5])) # 5 (single bar)
print(largest_rectangle([0, 0, 0])) # 0 (all zero)
print(largest_rectangle([3, 0, 3])) # 3 (zero splits)分治法替代方案
柱状图问题也可以使用分治法解决：以高度最小的柱条为分割点，递归解决左右两半，再将两半的结果与使用最小高度覆盖整个宽度的矩形进行比较。平均时间复杂度为 O(n log n)，但对于已排序的输入，最坏情况的复杂度为 O(n²)。
单调栈方法在最坏情况下的复杂度严格更优，为 O(n)。不过，理解分治法能够加深对问题的直觉，并说明为什么任意片段中的最小高度柱条始终是覆盖整个宽度的矩形的限制因素。
def largest_rectangle_dc(heights, lo=0, hi=None):
if hi is None:
hi = len(heights) - 1
if lo > hi:
return 0
# Find the index of the minimum height in [lo, hi]
min_idx = lo
for i in range(lo, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
# Three options:
# 1. Max rect entirely in left half
# 2. Max rect entirely in right half
# 3. Max rect spanning entire [lo, hi] with height = min
full_width_area = heights[min_idx] * (hi - lo + 1)
left_area = largest_rectangle_dc(heights, lo, min_idx - 1)
right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
return max(full_width_area, left_area, right_area)
print(largest_rectangle_dc([2, 1, 5, 6, 2, 3])) # 10柱状图模式：子数组计数
还有一个使用相同栈技术的相关问题：计算柱状图中最小元素等于某个目标值的子数组数量。解决方法是计算每个柱条的 PSE 和 NSE，然后使用公式 (i - pse[i]) × (nse[i] - i)，该公式统计柱条 i 作为最小值时所对应的子柱状图数量。
这种“左侧数量 × 右侧数量”的技术出现在多个 LeetCode 问题中：子数组最小值之和（907）、所有字符均不重复的子字符串计数，以及贡献值计算类问题。单调栈可以在 O(n) 时间内计算 PSE 和 NSE，从而使每个元素的贡献能够在 O(1) 时间内完成。
def sum_of_subarray_minimums(arr):
n = len(arr)
pse = [-1] * n # previous strictly smaller element
nse = [n] * n # next smaller or equal element
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
MOD = 10**9 + 7
total = 0
for i in range(n):
left_count = i - pse[i] # subarrays where i is leftmost min
right_count = nse[i] - i # subarrays where i is the min
total += arr[i] * left_count * right_count
return total % MOD
print(sum_of_subarray_minimums([3, 1, 2, 4])) # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3])) # 444实用面试技巧
在面试中遇到直方图问题时，请按照以下清单进行：
- 澄清：高度可以为 0 吗？输出是什么——面积、索引还是数量？
- 从暴力方法开始，并说明 O(n²) 或 O(n³) 的复杂度
- 说明每根柱子的贡献取决于它向左和向右延伸到最近更矮柱子的范围
- 引入 PSE/NSE → 单调栈 → O(n) 解法
- 处理哨兵技巧（append 0），以简化代码
- 在白板上跟踪一个小例子
常见追问：扩展到二维（最大矩形）。请展示如何将其归约为 n 个直方图问题，每个问题为 O(n)，总复杂度为 O(m×n)。
# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel forces final pops
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Verify all test cases from earlier
test_cases = [
([2, 1, 5, 6, 2, 3], 10),
([6, 7, 5, 2, 4, 5, 9, 3], 16),
([1], 1),
([2, 0, 2], 2),
([], 0),
]
for heights, expected in test_cases:
if not heights:
result = 0
else:
result = largest_rectangle_in_histogram(heights)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {heights} => {result} (expected {expected})')子数组范围和及类似变体
PSE/NSE 技术可以推广到多个 LeetCode 问题。子数组范围和（2104）要求计算所有子数组中（最大值 - 最小值）的总和。这等于（子数组最大值之和）减去（子数组最小值之和），两者都可以用单调栈在 O(n) 时间内计算。队列中可见的人数（1944）使用递减栈，每次 pop 都会计数一个可见的人。识别这类问题的关键，是注意到“对于每个元素，它最多能支配多远？”这一表述——答案总是使用单调栈实现 PSE/NSE。
def sum_subarray_ranges(nums):
n = len(nums)
# Sum of subarray max - sum of subarray min
def contrib(arr, is_max):
# Count contribution of each element as max (or min)
n = len(arr)
left = [0]*n; right = [0]*n
stack = []
for i in range(n):
while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n))
return contrib(nums, True) - contrib(nums, False)
print(sum_subarray_ranges([1, 2, 3])) # 4
print(sum_subarray_ranges([1, 3, 3])) # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1])) # 59快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中您学到了：对于每根柱子，包含它的最大矩形的边界由两侧最近的更矮柱子（PSE 和 NSE）确定，单调递增栈通过在柱子出栈时同时找到两侧边界，在一次 O(n) 遍历中计算所有 PSE/NSE 边界，以及使用 append 追加哨兵 0 可确保所有柱子都从栈中弹出，从而将代码简化为单个循环。接下来，我们将应用单调双端队列，在 O(n) 时间内求解滑动窗口最大值。
常见问题解答
「直方图中的最大矩形」课时是免费的吗？
是的 — 「直方图中的最大矩形」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「直方图中的最大矩形」这节课中我会学到什么？
使用单调栈跟踪左边界，并在一次遍历中计算能够容纳于直方图中的最大矩形面积。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「直方图中的最大矩形」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 单调栈：递增与递减
- 直方图中的最大矩形
- 使用单调双端队列求滑动窗口最大值
- 接雨水：栈与双指针