单调栈避坑实录：下一个更大元素类题型的建模方法与 4 个变体

「找下一个更大元素」是那类乍看简单、数据量一上来就崩的题：对数组每个元素，找出它右侧第一个比它大的元素位置。暴力做法对每个元素向右扫一遍，O(n²) 在 10⁴ 规模还能挣扎，10⁵ 直接超时。单调栈用一趟扫描解决全部元素，思路却反直觉——它不正面去找答案，而是维护一列「还没找到答案的元素」，让未来的大元素主动找上门来。

初次接触最容易卡住两个点：栈里到底存什么（值还是下标）、什么时候弹栈什么时候入栈。这篇文章从建模动机讲起，把主题型和四个变体一次讲透，代码全部给出可运行的 Python 实现，最后把踩过的坑汇总成清单。

思路推导：弹出的瞬间，答案就出现了

单调栈的建模核心是一句不变量：栈内的元素从栈底到栈顶保持单调，每个栈内元素都还没有得到自己的答案；新元素到来时，所有「比新元素小」的栈内元素找到了答案——就是当前这个新元素——于是被弹出。以「下一个更大元素」为例，栈内从底到顶严格递减：新元素 x 入栈前，把所有小于 x 的栈内元素逐个弹出，每弹出一个就记录「它的下一个更大元素是 x」；弹完之后 x 入栈，继续等待自己的答案。

变体	栈内单调方向	答案产生时机	关键改动
下一个更大元素	栈底到栈顶递减	新元素入栈前弹出时	基础形态
前一个更大元素	栈底到栈顶递减	弹栈结束后查看栈顶	反向遍历或改记录时机
循环数组	同基础形态	同基础形态	遍历 2n−1 次并对下标取模
柱状图最大矩形	栈底到栈顶递增	弹出时用两侧边界算宽度	哨兵元素统一收尾

为什么每个元素至多进出栈一次就能覆盖所有答案？因为某个元素的答案如果存在，必然是它右侧第一个比它大的元素；当那个大元素入栈时，所有仍未出栈且更小的元素恰好按位置从近到远排列在栈中，逐个弹出即逐个得到答案。单调性保证「右侧第一个更大」与「弹出时刻」严格对应——这就是 O(n) 复杂度的来源，也是为什么栈内必须维持单调：一旦乱序，弹出顺序与答案顺序就脱钩了。

实操代码：主题型与四个变体的完整实现

先写基础形态「每日温度」：对每天回答还要等几天才有更暖的天。栈里存下标而不是值——因为弹出时既要用值比较，也要用下标写答案，存下标一举两得：

# 每日温度：找右侧第一个更大元素的距离（Python）
def daily_temperatures(temperatures: list[int]) -> list[int]:
    ans = [0] * len(temperatures)   # 无更大元素时保持 0
    stack: list[int] = []           # 栈内存下标，对应温度从底到顶递减
    for i, t in enumerate(temperatures):
        # 当前温度比栈顶温度高：栈顶元素的答案就是 i，逐个结算弹出
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j          # 距离 = 当前下标 - 答案下标
        stack.append(i)             # 当前元素入栈，等待自己的答案
    return ans                      # 留在栈中的元素天然无答案，保持 0

第一个变体是循环数组：数组首尾相接，下一个更大元素可以绕回来找。技巧是遍历 2n−1 个「虚拟下标」，对真实下标取模访问元素；绕完第二圈时栈内剩余元素确认真无答案。用假想下标统一处理，不需要真的复制数组：

# 下一个更大元素 II：循环数组版本（Python）
def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)
    ans = [-1] * n                  # 默认无更大元素
    stack: list[int] = []
    for i in range(2 * n - 1):      # 虚拟遍历两轮，覆盖绕环查找
        t = nums[i % n]             # 取模映射回真实元素
        while stack and nums[stack[-1]] < t:
            ans[stack.pop()] = t    # 结算：弹出元素的下一个更大值
        if i < n:
            stack.append(i)         # 第二轮只做弹栈结算，不再入栈
    return ans

第二个变体是「柱状图中最大的矩形」，单调栈最有含金量的应用。对每根柱子，以它的高度为矩形高的极限宽度由两侧第一个更矮柱子决定——左右边界各需一次「下一个更小元素」。用单调递增栈一次遍历同时得到两侧边界：弹出某根柱子时，它右侧第一个更矮柱子是当前下标，左侧第一个更矮柱子是弹出后的新栈顶。结尾的清栈用一个高度为 0 的哨兵柱子统一触发，避免单独写收尾逻辑：

# 柱状图中最大的矩形：单调递增栈 + 哨兵（Python）
def largest_rectangle_area(heights: list[int]) -> int:
    heights = heights + [0]         # 末尾哨兵：高度 0，强制清空全部栈
    stack: list[int] = []           # 存下标，高度从底到顶严格递增
    best = 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:  # 当前更矮，栈顶柱子的右边界已定
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1    # 左边界 = 新栈顶（第一个更矮者）
            best = max(best, height * (i - left - 1))  # 宽度不含两侧更矮柱
        stack.append(i)
    return best

宽度计算 i - left - 1 是这题的核心：左开右开的区间长度，两侧各减掉更矮的柱子。另外注意栈内比较用了严格大于——遇到等高柱子时不弹出、让等高柱子继续压栈，最后弹出的那根等高柱子会把整段等高区域的宽度一次算足，结果不受影响；把条件改成 >= 同样正确，但绝不能一边严格一边非严格地混用两边边界。

剩下两个方向上的变体（找前一个更大元素、找下一个更小元素）不需要新骨架：前者反向遍历数组、复用同一套弹栈逻辑；后者把比较方向翻转即可。变体万变不离「谁在什么时候弹、弹出时用哪两侧信息算答案」这三个问题，建模时把这三问答出来，代码基本就定型了。

复杂度收个尾：主题型与全部变体中，每个下标至多入栈一次、出栈一次，循环体内的操作均摊 O(1)，总时间 O(n)、空间 O(n)。柱状图变体借助哨兵把「遍历后清栈」合并进主循环，代码少一段、逻辑少一个分支，属于典型的用一个小技巧换显著复杂度下降的案例。

建模与避坑总结

1. 栈里永远存下标不存值。结算答案需要距离（下标差）或边界（下标），只存值就得额外维护位置映射，徒增出错面；比较时通过下标取值即可，两不耽误。
2. 严格与非严格单调的选择要成对考虑。「找严格更大」用 栈顶 < 当前 弹出，「找大于等于」用 栈顶 <= 当前 弹出；柱状图等需用两侧边界的题，两个方向的严格性会互相配合，混用会导致宽度计算出错，落笔前把「等于算不算更大」确认清楚。
3. 哨兵是清栈的通用手段。单调递增栈末尾补一个极小值、递减栈补一个极大值，能强制所有剩余元素在主循环内弹出，避免复制一段「清栈收尾」代码——收尾逻辑单独写一遍是单调栈题重复 bug 的常见来源。
4. 循环数组用虚拟下标 + 取模，不要复制数组。遍历 2n−1 个虚拟位置在逻辑上等价于绕环两圈，第二圈只结算不入栈；真的拼接数组虽然也能过，但多占了 O(n) 空间且掩盖了「绕环」这个建模本质。
5. 用「谁还没找到答案」检查栈语义。调试时打印栈内容，先问每个栈内元素「它的答案是不是还没出现」；如果出现栈内元素按位置乱序，说明比较方向写反，答案必然错——这个自检比逐行读代码快得多。

单调栈的适用信号可以概括为：题目在问「某个方向上第一个比当前元素大/小的元素」，或者区间极值决定答案、区间边界恰好是第一个破坏单调性的位置。抓住「弹出即结算」这一瞬间，主题型与所有变体就都收敛到同一个模板上了。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。