想象你走进一家叫“星光剧场”的剧院，门口排着一条长长的队伍。每个人的胸前都贴着一个数字——那是他们的“身高值”。剧场经理接到一个任务：队伍不断往前移动时，他必须随时报出“当前能看到的最高的人”以及“每个人身后第一个比他高的人是谁”。如果把所有人的身高都记住，队伍一大就累死了。经理灵机一动：与其记住所有人，不如只保留那些“还有机会当选”的候选人，用一个有序的清单实时淘汰掉永远不可能出头的人。这个只保留候选者的思路，就是单调栈与单调队列的灵魂：在“有序淘汰”中享受 O(n) 的线性时间。 本文会用这个“剧场排队”的故事贯穿始终，带你从零理解单调栈（monotonic stack）和单调队列（monotonic queue）。你会看到它们如何用“入栈/出栈、入队/出队”几个简单动作，优雅地解决下一个更大元素、滑动窗口最值、柱状图最大矩形、接雨水，甚至优化 DP 状态转移。学完这块，你能高效处理海量数据流中的“最近更大值/区间极值”问题，这在实时系统、量化分析和推荐引擎里都是高频刚需。

岗位关联

对 AI 从业者而言，单调栈/单调队列是“数据流极值工程”的基石：你能用 O(n) 时间从千万级序列中提取滑动窗口特征，无论是做特征工程、序列建模还是延迟优化，都多了一件趁手的兵器。

目录
  1. 可视化演示
  2. 单调思想
  3. 单调栈维护
  4. 下一个更大元素
  5. 单调队列维护
  6. 滑动窗口最值
  7. 柱状图最大矩形
  8. 接雨水问题
  9. 复杂度与应用
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示单调栈求下一个更大元素的出栈入栈过程、单调队列维护滑动窗口最值的双端操作、以及两种数据结构特性对比。

本节配有交互动效（进入视口后自动加载，约 3KB）。

单调栈：下一个更大元素 橙色=当前处理元素 逐个入栈 栈顶NGE: O(n) monotonic 递减栈维护右侧首个更大元素

单调思想

回到星光剧场。经理发现，队伍里如果前面已经站着一个身高 180 的人，那么排在他后面的身高 160 的人，在“从前往后看谁最高”的问题里永远不可能被选中——因为 180 比 160 更高、也站得更靠前。与其把所有 160 都记住，不如当场淘汰。所谓“单调”，就是让候选人的身高始终朝一个方向有序变化：要么越往后越高，要么越往后越矮。只要维持这个顺序，每次只看最边上那一个候选者，就能立刻回答问题。

这个思路落到数据结构上，就是单调栈和单调队列。它们不存所有数据，只存“还有资格当选”的候选下标，并且让这些下标对应的值保持单调。用一点空间上的“牺牲”（丢掉中间信息），换来每次操作 O(1) 的平均代价。前面剧场经理只需要维护一个“从高到矮”的候选名单，就能瞬间知道当前最高的人是谁。

为什么总复杂度是 O(n) 而不是 O(n²)？因为每个元素虽然可能被比较多次，但它真正“入栈/入队”和“出栈/出队”各自最多发生一次。下面的公式把这个均摊账算清楚。

经理不会重复打量同一个人很多次：来的时候就看一眼，被淘汰时再记录一笔，队伍再长，时间也是线性的。这就是单调思想最迷人的地方：用“有序淘汰”换线性时间。

T(n)=∑i=1nO(1)=O(n)\displaystyle T(n)=\sum_{i=1}^{n}O(1)=O(n)
每个元素最多进一次、出一次，所以 n 个元素总共只有约 2n 次基本操作，复杂度是线性。
  1. 基本操作计数每个下标至多被压入一次，也至多被弹出一次，单次操作是常数时间。
    T单元素=O(1)T_{\text{单元素}}=O(1)
  2. 枚举所有元素求和对 n 个元素各自常数次操作做累加。
    S=∑i=1nO(1)\displaystyle S=\sum_{i=1}^{n}O(1)
  3. 化简渐进复杂度n 个常数相加仍是一个关于 n 的线性函数。
    T(n)=O(n)\displaystyle T(n)=O(n)

单调栈维护

经理手上有一个“高个子档案”，按从下到上从高到矮的顺序叠放。新来的客人 x 站到档案最上面之前，要先检查：如果最上面的客人比 x 矮，那么这位矮客人的“身后第一个更高者”就是 x，可以当场记录并移出档案。反复这样做直到栈顶不再比 x 矮，再把 x 放上去。这个“矮个淘汰”的过程，就是单调栈的维护规则。

严格来说，我们用一个数组模拟栈，栈里存的是下标而不是值，因为下标能同时给出位置和值。维护的单调性是：从栈底到栈顶，对应的数值严格递减。为什么是“严格”？因为题目要的是“更高”而不是“一样高”，身高相等的人不会被算作“更高者”，所以相等时也要把旧人弹出，让新人占据位置。

单调栈的核心操作只有两条：入栈前先循环弹出所有不满足单调性的栈顶；然后把当前下标入栈。由于每个下标最多被弹出一次，整个维护过程是均摊 O(n) 的。下面这条不变式需要刻进脑子里。

想象档案夹：每次来新人，就把压在顶上一串“矮个子”抽走，再把自己的卡片盖在最上面。抽走的卡片上会被经理写上答案：那个新人就是它身后第一个更高者。单调栈不是玄学，它只是把“未来注定被遮挡”的候选人提前清理掉。

as1>as2>⋯>ask\displaystyle a_{s_1}>a_{s_2}>\cdots>a_{s_k}
栈中下标 s1 < s2 < …… < sk，但它们对应的值从栈底到栈顶严格递减。
  1. 下标有序s1 是最先入栈的，位置最靠左。
    s1<s2<⋯<sks_1<s_2<\cdots<s_k
  2. 值单调栈底值最大，栈顶值最小。
    as1>as2>⋯>aska_{s_1}>a_{s_2}>\cdots>a_{s_k}
  3. 弹出条件遇到新值 x，只要栈顶值小于等于 x 就弹出。
    atop(S)≤x⇒pop\displaystyle a_{top(S)}\le x \Rightarrow \text{pop}
  4. 压入新值弹出结束后，把当前下标压入栈顶，单调性自动恢复。

下一个更大元素

现在剧场要回答一个具体问题：对队伍里每个人，找到他身后第一个比他高的人；如果身后没有更高的人，答案记为 -1。朴素做法是每个人往后逐个看，最坏 O(n²)。经理用单调栈一行行维护：从左到右处理每个新来的人 x，每弹出一个栈顶 s，就说明 x 是 s 身后第一个更高者，立刻把答案 ans[s] 记为 x 的值。

为什么弹出的那个人答案一定是“当前 x”而不是更后面的人？因为 x 是从左到右扫描中第一个比 s 高的人；如果中途还有人比 s 高，s 早就被更早的流程弹出了。扫描结束后，栈里剩下的人都是“身后没有更高者”的，答案保持 -1。整个过程每个元素进栈一次、出栈一次，答案在出栈时一次性写死。

用公式表达就是：对于下标 i，答案是第一个满足条件 j>i 且 a_j > a_i 的 j 对应的值。

这个故事里，每个人被“更高的人”领走时，自己的答案就定格了；没人来领的，就安静地站在栈底，带着 -1 结束。单调栈把“向后看”的暴力扫描，换成了“遇到高个就结算”的线性流程，这就是 O(n) 的魔力。

ans[i]={ajif j>i and aj>ai−1otherwise\displaystyle ans[i]=\begin{cases} a_j & \text{if } j>i \text{ and } a_j>a_i \\ -1 & \text{otherwise} \end{cases}
出栈即结算：谁把你弹出栈，谁就是你的“下一个更大元素”。
  1. 初始化答案先把所有位置答案设为 -1。
    ans=[−1,−1,…,−1]\displaystyle ans=[-1,-1,\ldots,-1]
  2. 扫描当前元素 x从左到右依次处理 a_i。
    x=aix=a_i
  3. 循环弹出栈顶只要栈非空且栈顶值小于 x，就弹出栈顶 s 并结算答案。
    ans[s]=x\displaystyle ans[s]=x
  4. 压入当前下标当前下标成为新的候选者。
    push(i)\displaystyle push(i)
  5. 扫描结束栈中剩余元素没有更大者，保持 -1。

单调队列维护

如果经理的问题是“当前窗口里谁最高”，他需要的是一个能两头操作的“冠军候选席”。候选席的左边是队头，右边是队尾，席位里的身高从队头到队尾严格递减。新客人到来时，先看队尾：如果队尾的人比新客人矮或相等，这个人以后永远不可能成为窗口最大值（因为新客人更高、更晚失效），直接淘汰；一直淘汰到队尾比新客人高，再把新客人从队尾放进候选席。

同时，窗口会右移，队头的候选人如果下标已经滑出窗口左边界，就必须从队头离开，因为它已经“过期”了。经过这两步维护，候选席的队头永远是当前窗口的最大值下标。注意这里用了双端队列（deque）：队头负责过期淘汰，队尾负责“更强新人淘汰旧人”。

单调队列的不变式和单调栈很像，只是多了一个“两头都管”的动作。

候选席的规矩很简单：新来的更强，就把弱小的旧人踢出队尾；位置太老的，就从队头请出去。剩下坐在第一把交椅上的，永远是当前窗口最亮的那颗星。

aq0>aq1>⋯>aqm,q0<q1<⋯<qm\displaystyle a_{q_0}>a_{q_1}>\cdots>a_{q_m},\quad q_0<q_1<\cdots<q_m
队头下标最老、值最大；队尾下标最新、值最小。
  1. 队尾淘汰while 队列非空且队尾值 ≤ 当前值，弹出队尾。
    aqm≤x⇒pop_back\displaystyle a_{q_{m}}\le x \Rightarrow pop\_back
  2. 队尾入队把当前下标压入队尾。
    qm+1=i\displaystyle q_{m+1}=i
  3. 队头过期如果队头下标小于窗口左边界，弹出队头。
    q0<L⇒pop_front\displaystyle q_0<L \Rightarrow pop\_front
  4. 读取最大值当前窗口最大值为队头对应的值。
    max⁡=aq0\displaystyle \max=a_{q_0}

滑动窗口最值

滑动窗口问题给定一个数组和一个固定长度 k，要求输出每个位置 i 对应的窗口 [i-k+1, i] 里的最大值。最笨的方法是对每个窗口都扫一遍，时间复杂度 O(n·k)。用单调队列，窗口每向右移动一格，只需要做一次“队尾淘汰”、一次“入队”和一次“队头过期检查”，然后取队头即可。

算法流程非常清晰：先让窗口前 k 个元素依次经过单调队列的“入队考验”；之后从 i=k 到 n-1，每处理一个新元素，就把队头下标小于 i-k+1 的过期者弹出，再把新元素经过队尾淘汰后入队，最后读取队头作为窗口答案。因为每个元素只进出一次，总时间是 O(n)。

用数学语言说，单调队列让“在窗口内求最大”这个原本要 O(k) 的操作，被压成了 O(1) 的查表。

剧场经理每看到一个新客人，只需抬头看候选席第一把交椅，就能报出当前窗口身高最高的人。窗口哗啦哗啦地滑，候选席安安静静地换人，答案永远信手拈来。

max⁡j∈[i−k+1, i]aj=aq0\displaystyle \max_{j\in[i-k+1,\,i]}a_j=a_{q_0}
窗口最大值不用遍历整个窗口，队头下标指向的元素就是答案。
  1. 定义窗口区第 i 步的窗口覆盖从 i-k+1 到 i 的下标。
    j∈[i−k+1, i]j\in[i-k+1,\,i]
  2. 维护单调队队内值严格递减，队头是最大候选。
    q0=arg⁡max⁡j∈窗口ajq_0=\arg\max_{j\in窗口}a_j
  3. 队头过期判断队头下标小于左边界就弹出。
    q0<i−k+1⇒pop_frontq_0<i-k+1\Rightarrow pop\_front
  4. 问题答案把队头值写入结果数组。
    ansi=aq0ans_i=a_{q_0}

柱状图最大矩形

剧院有一排柱子，每根柱子高度不一，经理想在里面圈出一个面积最大的矩形。矩形必须完全落在柱状图内，且底边贴着地面。换个说法：对于每根柱子，如果它作为矩形的高度 h_i，那么矩形能向左延伸到哪里、向右延伸到哪里？答案是左右两边第一个比它矮的柱子——因为再往远走，柱子矮了，矩形高度就撑不起来了。

单调栈在这里的作用是：维护一个从栈底到栈顶递增的栈（值从小到大）。从左到右扫描，当遇到当前柱子比栈顶矮时，栈顶柱子就找到了它的右边界（当前下标），而它左边界就是弹掉它之后的新栈顶下标。于是以它为高的最大矩形宽度 = 右边界 - 左边界 - 1。

面积公式非常简洁：高是 h_i，宽是左右两个“更矮边界”之间的距离。

每根柱子就像剧场里的一位“矮个子守卫”：左右两边一出现更矮的墙，它的舞台范围就被锁死了。经理只要用单调栈把每根柱子的左右边界找齐，最大矩形自然浮出水面。

Si=hi×(ri−li−1)\displaystyle S_i=h_i\times(r_i-l_i-1)
每个柱子都被“更矮的墙”夹住，宽就是两道墙之间的距离减一。
  1. 左边界 l_i栈中它下面那个下标，是左边第一个比它矮的柱子。
    li=top(S) after popl_i=top(S)\ \text{after pop}
  2. 右边界 r_i触发弹出的当前下标，是右边第一个比它矮的柱子。
    ri=ir_i=i
  3. 宽度两个边界不相邻，中间隔了 r-l-1 根柱子。
    wi=ri−li−1w_i=r_i-l_i-1
  4. 面积高乘宽，更新全局最大。
    Si=hi×wiS_i=h_i\times w_i

接雨水问题

剧场的露天广场上有一排高低不平的墙，下大雨后低洼处会积水。每根柱子处能积多少水，取决于它左右两边最高的墙中较矮的那一个。直观公式是：每个位置 i 的积水量 = min（左边最高墙，右边最高墙） - 当前高度。这个公式好懂，但要分别预处理左右最大值，需要两次扫描和 O(n) 空间。

单调栈提供另一种更优雅的“按层累加”视角：维护一个单调递减栈。扫描到当前柱子 r 时，如果它比栈顶高，说明栈顶柱子 p 是一个“坑底”，它的左墙是弹出它之后的新栈顶 l，右墙就是当前柱子 r。这一层能存的水量是 (min(h_l, h_r) - h_p) × (r - l - 1)，把每次弹出的坑底都累加进答案。

这个方法的精妙之处在于：它不是按柱子算水，而是按水面的一层一层算水，每次弹出栈顶时把那一条“水平带”的积水一次性加上。

每一滴雨水都被经理按“层”结算：坑底被更高的墙发现时，它头顶那一层水立刻称重入账。看起来是在处理墙的高度，实际上是在处理水面，这就是单调栈解决接水问题的妙处。

V=∑p∈popped(min⁡(hl,hr)−hp)×(r−l−1)\displaystyle V=\sum_{p\in popped}(\min(h_l,h_r)-h_p)\times(r-l-1)
每弹出一个“坑底”，就结算左右两墙夹出的那一层雨水。
  1. 弹出坑底 p当前柱子 r 比栈顶高，栈顶是坑底。
    hr>htop(S)h_r>h_{top(S)}
  2. 找到左墙 l弹出后新的栈顶是左墙。
    l=top(S)l=top(S)
  3. 计算层高左右墙较矮者减去坑底高度。
    layer=min⁡(hl,hr)−hp\displaystyle layer=\min(h_l,h_r)-h_p
  4. 计算层宽两墙之间的距离。
    width=r−l−1width=r-l-1
  5. 累加水量本层水量加入总答案。
    V+=layer×width\displaystyle V+=layer\times width

复杂度与应用

最后算一笔总账。无论是单调栈还是单调队列，每个元素最多入栈/入队一次、出栈/出队一次，所以总时间是 O(n)，额外空间是 O(n)（最坏情况栈或队列装下所有元素）。这种“每个元素操作常数次”的性质叫均摊 O(n)，它比“严格每步 O(1)”更宽松，但总时间依然线性。

单调性还有一个大招：优化某些 DP 状态转移。比如状态转移方程里要取“前 k 个里的最大值”，朴素做法是每个状态都扫 k 项，O(n·k)；如果把候选 dp[j] 放进单调队列，队头就是最优值，转移变成 O(1)，总复杂度降到 O(n)。这类“滑动窗口型 DP”在序列决策问题里非常常见。

剧场经理最后悟出一个道理：凡是“窗口内选最优”的问题，都可以让候选者排成一个单调的队，每次只取队头。数据再多，只要排队规则不变，处理时间就是线性的。工程里遇到滚动窗口极值、频率统计、序列决策优化，想想这个候选席，你会少写很多重循环。

dp[i]=max⁡j∈[i−k, i−1]dp[j]+w(i)\displaystyle dp[i]=\max_{j\in[i-k,\,i-1]}dp[j]+w(i)
用单调队列维护窗口内 dp[j] 的最大值，转移一步到位。
  1. 朴素转移每次枚举窗口内所有 j 找最大 dp[j]。
    O(nk)\displaystyle O(nk)
  2. 入队候选dp[i-1] 进入单调队列，淘汰窗口内更小的旧 dp 值。
    while qback≤v:pop_back\displaystyle \text{while } q_{back}\le v: pop\_back
  3. 过期出队队头下标小于 i-k 则弹出。
    q0<i−k⇒pop_front\displaystyle q_0<i-k \Rightarrow pop\_front
  4. 最优转移队头对应的 dp[j] 就是窗口最大值。
    dp[i]=dp[q0]+w(i)\displaystyle dp[i]=dp[q_0]+w(i)

AI 应用场景

量化交易中的滑动窗口最高价

阶段：实时特征工程 / 数据预处理

解决的问题：传统做法对每个 tick 都重新扫描过去 60 秒的最高价，窗口每滑动一次就 O(k)，在每秒上千笔交易的行情流里 CPU 开销爆炸。用单调队列维护滑动窗口最高价，每个 tick 只需 O(1) 更新，整体 O(n)，让高频特征计算能扛住百万级消息。

具体案例：某量化系统需要实时输出“过去 5 分钟最高价、最低价”作为突破信号。改造前 CPU 占用 70%，改用单调队列后降到 8%，延迟从几十毫秒降到微秒级。

服务监控中的滑动窗口峰值 QPS

阶段：稳定性监控 / 异常检测输入

解决的问题：监控系统要报告过去 300 秒的峰值 QPS 和 99 分位延迟，朴素滑窗统计在窗口很大时成本过高。用单调队列维护窗口最大值，内存里只存候选下标，无论窗口多大，每次上报都是 O(1)。

具体案例：某云厂商的监控组件用单调队列计算滚动窗口峰值，把 100 个服务实例的监控开销从每分钟千万次比较降到百万次，告警响应速度提升明显。

推荐系统里的频控 DP 优化

阶段：策略优化 / 在线决策

解决的问题：广告频控要求“最近 k 次曝光内最多选 n 次”，可建模成滑动窗口 DP，状态转移需要窗口内最大值。用单调队列优化后，O(n·k) 的决策变成 O(n)，线上策略每轮更新的耗时大幅下降。

具体案例：某推荐团队在预算分配策略中引入单调队列优化 DP 转移，策略更新时延从 120ms 降到 15ms，同时保持了同等的投放效果。

Python 演示

python29 行
from collections import deque def sliding_window_max(nums, k):    dq = deque()    res = []    for i, x in enumerate(nums):        while dq and nums[dq[-1]] <= x:            dq.pop()        dq.append(i)        if dq[0] <= i - k:            dq.popleft()        if i >= k - 1:            res.append(nums[dq[0]])    return res def next_greater_element(nums):    n = len(nums)    ans = [-1] * n    stack = []    for i in range(n):        while stack and nums[stack[-1]] < nums[i]:            ans[stack.pop()] = nums[i]        stack.append(i)    return ans if __name__ == "__main__":    nums = [2, 1, 5, 3, 4, 7, 6, 8]    print("sliding window max:", sliding_window_max(nums, 3))    print("next greater element:", next_greater_element(nums))
目的：用单调队列求滑动窗口最大值，用单调栈求每个元素的下一个更大元素，两者都是 O(n) 时间复杂度。
  1. from collections import deque双端队列是单调队列的实现基础，两头都能以 O(1) 操作。
  2. while dq and nums[dq[-1]] <= x:从队尾弹出所有“不可能再当最大值”的旧候选。
  3. if dq[0] <= i - k:队头下标滑出窗口左边界，说明该候选已过期，从队头移除。
  4. res.append(nums[dq[0]])队头就是当前窗口最大值，直接读取。
  5. while stack and nums[stack[-1]] < nums[i]:栈顶遇到比自己高的新元素，弹出并结算“下一个更大元素”。
  6. ans[stack.pop()] = nums[i]谁被弹出，谁的答案就是当前这个更大的值。
  7. stack.append(i)每个下标最终都会入栈，等待未来被更高者领走。

常见误区

误区我一开始以为单调队列就是把窗口里的所有元素都存下来，只是碰巧有序排列，这样我还能随便查第 k 大的值。

正解单调队列只保留“有可能成为最大值”的候选者。当一个新元素比队尾大时，队尾那些更小、更早失效的元素会被直接丢弃，它们永远不可能再成为窗口最大值。就像剧场候选席只留冠军候选人，被淘汰的人不会再有返场机会。如果需要随机访问窗口内所有元素，应该用别的结构。

为何常见：“队列”这个词会让人想到“存着全部元素”的普通队列，忽略了单调队列会主动丢数据的特性。

误区我之前写单调栈时，弹出条件总随手写 `<`，觉得等于时留一个在栈里也没关系，最多答案一样。

正解求“下一个更大元素”要求严格大于。如果栈里保留相等值，后面的相等元素永远不会把前面的相等元素弹出，前面元素的答案会错误地变成 -1。正确写法是 while stack and nums[stack[-1]] < x: 或 <= x 要根据题目“严格大于/大于等于”来选择。相等时通常要弹出旧者，让更靠后的候选者接替位置。

为何常见：初学者区分不清“严格单调”和“非严格单调”对答案的影响，忽略边界细节。

误区既然名字里有“单调”，我以为单调栈也能像线段树一样，随便给个 [l, r] 就返回最大值。

正解单调栈擅长的是“下一个更大元素”、柱状图边界这类单向相邻信息；单调队列擅长的是“固定长度滑动窗口”的极值。任意区间最值查询需要 RMQ、线段树或 ST 表。三种工具适用场景不同，不能因为都有“单调”二字就混用。

为何常见：看到“区间最值”就联想到学过的单调结构，没有区分“固定窗口”和“任意区间”。

误区我以为 O(n) 意味着代码里每个元素恰好被访问一次，所以看到 while 循环里可能反复比较就觉得它不可能是 O(n)。

正解单调结构的复杂度是“均摊 O(n)”。某个元素可能在弹出的 while 里被比较多次，但它入栈/入队一次、出栈/出队一次，总操作次数约为 2n，常数 2 不影响渐进复杂度。均摊分析和最坏情况分析是不同的视角，这里每个元素生命周期只进出一次，所以总体线性。

为何常见：把“O(n)“误解为”每轮循环只做一次操作”，不了解均摊分析的思想。

面试题

Q1. 单调队列最适合解决哪类问题？

单选题 · easy

  • A.数组排序
  • B.固定滑动窗口的最值← 正确答案
  • C.哈希冲突处理
  • D.图的最短路径

答案：B。单调队列在滑动窗口推进时维护候选极值，队头就是窗口最大值或最小值，适合窗口最值问题。排序、哈希和图路径都有更专门的算法。

Q2. 用单调栈求“下一个更大元素”时，扫描结束后栈中剩余元素的答案应该是多少？

单选题 · easy

  • A.0
  • B.自身值
  • C.-1← 正确答案
  • D.栈底值

答案：C。栈中剩余元素说明扫描过程中始终没遇到比它们更大的元素，即它们身后没有更高者，按题意答案记为 -1。就像剧场里一直没人来领走的人，等不到更高的候选人。

Q3. 求滑动窗口最大值时，窗口每右移一个位置，新元素应该从哪里进入单调队列？

单选题 · easy

  • A.队头
  • B.队尾← 正确答案
  • C.中间
  • D.替换队头

答案：B。新元素代表最新的候选者，必须从队尾进入。进入前先把队尾更小或相等的旧候选弹出，保证队列单调递减；队头仍是最新窗口的最大值。

Q4. 维护单调递减栈时，当前元素 x 大于栈顶元素，正确的操作是？

单选题 · mid

  • A.直接把 x 压入栈
  • B.弹出所有小于等于 x 的栈顶元素后再压入 x← 正确答案
  • C.把 x 放到栈底
  • D.清空整个栈

答案：B。要维持栈底到栈顶递减，必须先把破坏单调性的栈顶全部弹出，再压入 x。被弹出的元素此时也会得到它们的“下一个更大元素”答案。

Q5. 滑动窗口最大值问题中，某个元素从队尾被弹出的根本原因是？

单选题 · mid

  • A.它的下标已经过期
  • B.新元素比它大且比它更晚失效，它不可能再成为最大值← 正确答案
  • C.队列容量满了
  • D.它恰好等于窗口大小

答案：B。队尾弹出是“更强新人淘汰旧人”：新元素更大、位置更靠右，旧元素永远没机会再当最大值。下标过期是队头弹出管的事，两者不同。

Q6. 柱状图最大矩形问题中，若 h[i] 左右第一个比它矮的柱子下标分别为 l 和 r，则以 h[i] 为高的矩形宽度是？

单选题 · mid

  • A.r - l
  • B.r - l - 1← 正确答案
  • C.r - l + 1
  • D.r / l

答案：B。两个边界柱子本身比 h[i] 矮，不能计入矩形，所以矩形覆盖的是 l 和 r 之间的柱子，下标差再减一，即 r-l-1。

Q7. 关于用单调栈求“下一个更大元素”，下列说法正确的是？

多选题 · hard

  • A.每个元素至多入栈和出栈各一次← 正确答案
  • B.必须从后往前遍历才能保证正确
  • C.弹出栈顶元素时，当前元素就是它的下一个更大值← 正确答案
  • D.算法时间复杂度是 O(n log n)

答案：AC。每个元素进出栈各一次，所以是均摊 O(n)，A 正确 D 错误。从左到右遍历也能正确求解：弹出栈顶时，当前元素正是它右边第一个更大者，C 正确。B 的“必须”过于绝对。

Q8. 接雨水问题中，用单调栈求解时，栈中柱子高度从栈底到栈顶是？

单选题 · mid

  • A.单调递增
  • B.单调递减← 正确答案
  • C.完全无序
  • D.全部相等

答案：B。只有栈底到栈顶递减，当前柱子高于栈顶时，栈顶才是“坑底”，才能计算左右墙夹出的水层。递减栈保证了“坑”能被及时识别。

Q9. 单调队列优化 DP 时，dp[i] = max(dp[j]) + w，其中 j 落在长度 k 的滑动窗口内，下列说法正确的是？

多选题 · hard

  • A.队头对应窗口内最优的 dp[j]← 正确答案
  • B.新 dp 值从队尾入队前要弹出较小的旧值← 正确答案
  • C.窗口滑出范围的队头要弹出← 正确答案
  • D.队列中的值必须严格递增

答案：ABC。单调队列维护窗口内 dp[j] 的候选最大值，队头是最优值，A 正确；入队前淘汰更小的旧候选，B 正确；过期下标从队头弹出，C 正确；D 方向反了，队列中值应单调递减。

Q10. 用单调栈求柱状图最大矩形时，栈中柱子高度的关系是？

单选题 · mid

  • A.从栈底到栈顶单调递增← 正确答案
  • B.从栈底到栈顶单调递减
  • C.随机起伏
  • D.全部相等

答案：A。递增栈保证遇到更矮柱子时，栈顶能找到左右两侧第一个更矮边界。当前柱子比栈顶矮时触发弹出，同时结算以栈顶为高的矩形面积。