在数字编码任务中，我们常常需要为数组中的每个数字计算一个编码值，例如找到它右侧第一个比它大的数字的下标距离。如果使用双重循环逐一比较，当数据量变大时程序会明显变慢。单调栈能够将这类问题的时间复杂度从O(n^2)降低到O(n)，是优化Python代码的重要手段。
什么是单调栈
单调栈是一种栈结构，其中存放的元素保持严格递增或递减的顺序。当新元素入栈时，如果破坏了单调性，就不断弹出栈顶，直到满足要求。利用这个性质，我们可以在遍历数组时快速得到每个元素左边或右边第一个满足大小关系的元素。
案例背景
假设有一组数字编码 nums，我们需要生成结果数组 res，res[i] 表示在 nums 中 nums[i] 右侧第一个比它大的元素与它的下标差；如果不存在这样的元素，则记为0。下面先看暴力写法。
暴力解法
def encode_force(nums):
n = len(nums)
res = [0] * n
for i in range(n):
for j in range(i + 1, n):
if nums[j] > nums[i]:
res[i] = j - i
break
return res
print(encode_force([2, 1, 5, 3, 6]))
上面的代码使用了两层循环，最坏情况下每个数字都要向后扫描剩余所有元素，时间复杂度为O(n^2)。
单调栈优化
我们改用单调递减栈，栈中保存下标，对应的值从栈底到栈顶递减。遍历数组，当当前数字大于栈顶下标对应的数字时，就弹出栈顶并计算距离。
def encode_monostack(nums):
n = len(nums)
res = [0] * n
stack = [] # 存放下标，保持对应数字递减
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
res[idx] = i - idx
stack.append(i)
return res
print(encode_monostack([2, 1, 5, 3, 6]))
该实现只遍历了数组一次，每个下标最多入栈和出栈一次，时间复杂度为O(n)，在空间上仅使用了一个栈，额外空间为O(n)。
两种写法对比
| 方法 | 时间复杂度 | 适用规模 |
|---|---|---|
| 暴力循环 | O(n^2) | 小型数据 |
| 单调栈 | O(n) | 大型数据 |
小结
通过数字编码案例可以看到，单调栈把原本需要嵌套扫描的逻辑压缩为单次线性遍历。在Python开发中，遇到寻找最近更大更小元素、每日温度、下一个更大元素等问题时，优先考虑单调栈往往能显著提升程序性能。