题型识别#

看到“下一个更大元素”“左侧第一个更小元素”“柱状图最大矩形”“每日温度等待天数”这类描述，就可以先考虑单调栈。

如果每个元素都要和左右一串元素比较，暴力是 O(n^2)，而单调栈能把每个元素入栈出栈各一次，降到 O(n)。

维护规则#

以寻找左侧最近更小元素为例，栈内保持从栈底到栈顶递增。当前元素 x 来时，所有大于等于 x 的元素都不可能再成为后面元素的最近更小值，所以弹出。

1
def prev_less(nums):
2
    stack = []  # 存下标，nums[stack] 单调递增
3
    ans = [-1] * len(nums)
4

5
    for i, x in enumerate(nums):
6
        while stack and nums[stack[-1]] >= x:
7
            stack.pop()
8
        if stack:
9
            ans[i] = stack[-1]
10
        stack.append(i)
11

12
    return ans

怎么改成其他题#

• 找更大：把比较方向改成 <= 或 <。

• 找右侧：从右往左遍历，或在弹栈时结算被弹元素。

• 要距离：用当前下标减答案下标。

• 要数值：最后用下标回到原数组取值。

边界检查#

重复元素是单调栈里最容易出错的边界。比较时用 < 还是 <=，决定了相等元素能不能共存。题目如果要求“严格更小”，通常弹出 >=；如果允许“小于等于”，规则就要调整。

实战复盘#

学《单调栈模板整理》时，我会用三类样例验收：普通样例验证流程，边界样例验证空数组和单元素，重复样例验证相等元素的处理。只跑一个正向样例，很容易把比较符号写错还不自知。

算法文章还要写清复杂度来源。单调栈看起来有 while 循环，但每个元素最多入栈一次、出栈一次，所以总复杂度是 O(n)。这个解释比单独写一个结论更重要。

后续刷题时，可以先把题目翻译成“找左侧/右侧的更大/更小元素”。能完成这一步，模板才真正变成自己的工具。

最小验收样例#

验收《单调栈模板整理》时，我会把代码跑在递增、递减、重复元素和空输入上。单调栈尤其要看重复元素，因为比较符号的选择会直接影响答案。

如果能把每一步栈内元素画出来，就说明自己理解了维护规则；如果只能背代码，换一个方向或比较关系就很容易写错。

小结#

单调栈的核心是让栈里只保留未来仍有可能成为答案的元素。先想清比较关系和遍历方向，再写模板。