单调栈模式
应用单调栈，以 O(n) 的时间解决每日温度、柱状图中的最大矩形和下一个更大元素问题。
单调栈模式 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是单调栈
单调栈是一种在其元素之间维护有序不变量的栈。递增单调栈中的元素从栈底到栈顶递增；递减单调栈中的元素从栈底到栈顶递减。当新元素违反不变量时，会不断弹出元素，直到恢复不变量，然后再压入新元素。
这一简单机制可以在 O(n) 时间内回答“最近的更大元素”和“最近的更小元素”查询，而暴力方法通常需要使用 O(n²) 的嵌套循环。
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)下一个更大元素（LeetCode 496）
对于每个元素，寻找其右侧第一个严格更大的元素。O(n²) 的暴力方法会从每个位置向右扫描。单调栈方法是维护一个索引递减的栈。当遇到更大的元素时，弹出所有较小元素对应的索引——它们的“下一个更大元素”就是当前元素。栈中剩余的索引没有下一个更大元素，因此结果为 -1。
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]循环数组中的下一个更大元素
LeetCode 503“下一个更大元素 II”：问题相同，但数组被视为循环数组。到达末尾后，从开头继续查找。关键做法是遍历数组两次（索引从 0 到 2n-1），并使用 i % n 对原数组进行索引。只将范围 [0, n-1] 内的索引压入栈，以避免重复处理。
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]每日温度：完整解法
重新学习 LeetCode 739：对于每一天，需要等待多少天才能遇到更高的温度？单调栈保存温度按递减顺序排列的日期索引。当找到更暖的第 i 天时，从栈中弹出所有较冷的日期索引 j，并记录 result[j] = i - j。栈中剩余的日期从未遇到更暖的日子，因此其结果保持为 0。
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]前一个更小元素
“前一个更小元素”查询要求：对于每个元素，找出其左侧最近的更小值。请使用递增单调栈从左到右处理元素。在压入索引 i 之前，栈顶就是前一个更小元素（因为所有大于当前元素的元素，都已在之前触发弹出操作的插入过程中被弹出）。
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]直方图中的最大矩形
LeetCode 84“直方图中的最大矩形”：使用索引递增的单调递增栈。对于每个柱子，弹出所有高于当前柱子的柱子。对于每个被弹出的柱子 h，其右边界是当前索引 i，左边界是新的栈顶 + 1（如果栈为空则为 0）。面积 = h ×（右边界 - 左边界）。在末尾添加一个高度为 0 的哨兵，以强制弹出所有剩余柱子。
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1最大矩形（LeetCode 85）
LeetCode 85“最大矩形”将直方图问题扩展到二维二进制矩阵。对于每一行，计算累计柱高：如果 matrix[row][col] == '1'，则高度为该单元格及其上方连续 1 的数量。然后对每一行的高度数组应用“直方图中的最大矩形”算法。对于 m×n 矩阵，时间复杂度为 O(m × n)。
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6接雨水：栈方法
使用栈解决 LeetCode 42“接雨水”：维护一个索引递减的栈。当遇到更高的柱子时，就形成了一个凹槽。弹出凹槽底部；水的宽度为（当前索引 - 栈顶索引 - 1），高度为（当前柱高与新的栈顶柱高中的较小值 - 凹槽底部高度）。将所有贡献相加。时间复杂度：O(n)，空间复杂度：O(n)。
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9识别单调栈问题
以下迹象表明单调栈是合适的工具：问题要求查找下一个或前一个更大/更小元素；每个元素的答案取决于某个特定方向上的元素；或者暴力方法需要为每个元素向左或向右扫描，从而达到 O(n²) 的复杂度。栈会保存可能成为后续元素答案的候选项，并在更好的候选项出现时立即丢弃它们。
请始终提前确定：使用递增栈（用于查找下一个/前一个更小元素）还是递减栈（用于查找下一个/前一个更大元素），以及要从哪个方向处理元素。
O(n) 均摊分析
单调栈算法乍看之下可能是 O(n log n) 或 O(n²)，因为 for 循环内部包含 while 循环。但每个元素最多压入一次、弹出一次。压入操作总数为 n，弹出操作总数也最多为 n。因此，所有迭代的总工作量是 2n 次操作，均摊复杂度为 O(n)，而不是 O(n²)。
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*n单调栈不变量的选择总结
请根据查询类型选择栈的方向。对于下一个更大元素，使用递减栈——当前元素更大时弹出栈顶元素。对于下一个更小元素，使用递增栈——当前元素更小时弹出栈顶元素。对于最大矩形，使用递增栈，并在出现更矮的柱子时弹出元素。对于滑动窗口最大值，使用递减双端队列，并从两端移除元素。
在编码前先将不变量写在注释中，有助于理清逻辑并加快调试。
快速检查
请检验您对本课中“数据结构与算法——编程面试准备”概念的理解。
课程回顾
本课中您学到了：单调栈会在压入新元素前弹出违反不变量的元素，从而维护有序不变量；递减栈用于回答下一个更大元素查询，递增栈用于回答下一个更小元素查询；以及由于每个元素最多压入和弹出一次，总时间复杂度为 O(n) 均摊复杂度。接下来，我们将使用栈实现队列，并使用队列实现栈。
常见问题解答
「单调栈模式」课时是免费的吗？
是的 — 「单调栈模式」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「单调栈模式」这节课中我会学到什么？
应用单调栈，以 O(n) 的时间解决每日温度、柱状图中的最大矩形和下一个更大元素问题。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「单调栈模式」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。