单调栈：递增与递减
维护递增栈或递减栈，以 O(n) 的时间高效回答下一个更大元素和前一个更小元素查询。
单调栈：递增与递减 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是单调栈
单调栈是一种维护元素有序排列的栈（从栈底到栈顶始终递增或始终递减）。在压入新元素之前，我们会弹出所有违反单调不变量的元素。这种受约束的数据结构可以将原本需要 O(n²) 嵌套循环的问题优化为 O(n) 解法。
关键洞察是：每个元素最多被压入和弹出一次，因此在遍历整个数组的过程中，操作总数为 O(n)，而不是 O(n²)。当我们弹出某个元素的那一刻，就找到了它一直等待的答案。
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]下一个更大元素 I
下一个更大元素问题要求：对于每个元素，找到它右侧第一个大于它的元素。暴力的 O(n²) 双重循环速度太慢。使用单调递减栈可以在 O(n) 时间内解决。
从左到右处理元素。在压入当前元素之前，弹出栈中所有小于当前元素的元素——当前元素就是这些元素的下一个更大元素。处理完所有元素后，栈中剩余的元素右侧都不存在更大的元素（答案为 -1）。
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]下一个更大元素：追踪算法
让我们逐步追踪 [2, 1, 2, 4, 3]。我们维护一个由索引组成的单调递减栈，其中尚未找到其下一个更大元素。
- i=0，值=2：栈为空，推入 0。栈：[0]
- i=1，值=1：1 < 数组[0]=2，推入 1。栈：[0,1]
- i=2，值=2：pop 1（数组[1]=1 < 2），结果[1]=2；此时数组[0]=2 不 < 2，推入 2。栈：[0,2]
- i=3，值=4：pop 2（结果[2]=4），pop 0（结果[0]=4），推入 3。栈：[3]
- i=4，值=3：3 < 数组[3]=4，推入 4。栈：[3,4]
- 结束：栈 [3,4] 中的元素结果均为 -1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])前一个更小元素
单调栈也可以回答前一个更小元素（PSE）查询：对于每个元素，找到其左侧最近的更小元素。我们不再遇到更大元素时弹出，而是在遇到更大或相等的元素时执行 pop，并在推入当前元素之前，将栈顶记录为 PSE。
处理方向发生了变化：我们仍然从左到右处理，但不再在弹出元素时回答问题，而是在推入元素之前回答。此时的栈顶就是左侧最近的更小元素。如果栈为空，则左侧不存在更小元素（答案为 -1 或某个哨兵值）。
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]每日温度：等待更暖的日子
每日温度问题（LeetCode 739）：给定每天的温度，返回一个数组，其中每个元素表示等待更高温度所需的天数。这正是下一个更大元素的模式，只是我们不需要更大的数值，而是需要天数（索引差）。
使用由索引组成的单调递减栈。当我们在索引 i 处找到更高的温度时，pop 栈中所有满足 temps[j] < temps[i] 的索引 j，并设置 result[j] = i - j。剩余索引之后没有更高的温度（结果 = 0）。
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]递增栈与递减栈：分别何时使用
选择正确的栈方向至关重要：
- 单调递减栈（当前值 > 栈顶时 pop）：用于回答下一个更大元素和上一个更大元素查询。应用于每日温度、最大矩形和接雨水问题。
- 单调递增栈（当前值 < 栈顶时 pop）：用于回答下一个更小元素和上一个更小元素查询。应用于计算股票价格跨度和队列中可见人员数量。
请记住：导致 pop 的元素就是被弹出元素查询的答案——根据所维护的不变量，它可能是下一个更大元素，也可能是下一个更小元素。
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)循环数组中的下一个更大元素
下一个更大元素 II（LeetCode 503）：给定一个循环数组（首尾相接），找出下一个更大元素。关键是将数组处理两次，通过重复索引来实现：从 0 遍历到 2n-1，并使用 index % n 循环回数组开头。我们只推入 0 到 n-1 的索引（第一次遍历），这样就不会重复计数。
另一种方法是在第二次遍历时处理数组但不推入新索引，只执行 pop。这样无需真正复制数组，也能正确处理循环查找，同时将空间复杂度保持为 O(n)。
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]股票跨度问题
股票跨度问题：给定每天的股票价格，计算每天的跨度——价格小于或等于当天价格的连续此前天数。这实际上是上一个更大元素问题的另一种形式：跨度就是从今天向前到最近一个价格严格更高的日期之间的距离。
使用单调递减栈。处理第 i 天时，pop 所有价格 ≤ 当前价格的日期。如果栈不为空，跨度为 i - stack[-1]；如果栈为空，跨度为 i + 1（说明当前价格是截至目前的最高价）。然后推入 i。
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6用于计算队列中可见人员的单调栈
队列中可见人员数量问题：一些人站成一列，每个人都有一个身高。如果中间所有人的身高都同时小于两端的人，人员 i 可以看见人员 j（j > i）。这个问题使用单调递减栈。
从右到左处理。维护一个按身高单调递减的栈。对于每个人，计算其能看见多少人：pop 所有较矮的人（这些人可见，但之后会被挡住）；如果 pop 后栈不为空，再加 1（第一个更高的人也可见）。由于每个人最多被推入和弹出一次，整体时间复杂度为 O(n)。
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]O(n) 保证：为什么每个元素最多被推入和弹出一次
单调栈算法的 O(n) 时间保证来自一个简单的摊还分析：每个元素恰好被推入栈一次，最多被弹出一次。没有元素会被推入或弹出超过一次。因此，整个循环中的推入和 pop 操作总数最多为 2n，尽管嵌套循环看起来可能暗示 O(n²)，但总工作量仍为 O(n)。
在面试中，清楚地阐述这种摊还分析很重要。循环不会在每次迭代中运行 n 次——它只会弹出此前一直等待的元素，而这些元素一旦被弹出，就不会再回来。
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2n识别单调栈问题
如果问题要求查找最近的更大或更小元素、价格跨度、一列中的可见元素或基于柱状图的面积，那么它很可能需要使用单调栈。请留意这些关键词和模式：每个元素都需要从某个方向（左侧或右侧）的最近相关元素中得到答案。
如果暴力解法需要从每个元素向左或向右扫描（O(n²)），请用单调栈替代这种扫描。栈会“记住”候选答案，丢弃无关候选，并在恰好需要答案的时刻弹出正确结果。
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：单调栈会在推入元素之前，弹出违反不变量的元素，从而维护递增或递减顺序；递减栈可以回答下一个或上一个更大元素问题，而递增栈可以回答下一个或上一个更小元素问题；以及每个元素最多被推入和弹出一次，因此总时间复杂度为 O(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 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「单调栈：递增与递减」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 单调栈：递增与递减
- 直方图中的最大矩形
- 使用单调双端队列求滑动窗口最大值
- 接雨水：栈与双指针