单调栈与单调队列

单调栈与单调队列解决的不是「如何排序」，而是「如何让一个元素在恰当的时刻结算」。在线性扫描中，许多元素的答案依赖右侧第一个更大（或更小）元素；许多区间的最值又只关心仍可能胜出的候选。若逐个向右试探，问题很容易退化为 $O(n^2)$ 。单调结构把仍未结算、仍有资格成为答案的下标压缩在一条有序边界上：新元素到来时，它一次性淘汰一批候选；被淘汰者恰好获得答案，或被证明不再可能胜出。

本文把这种「候选—淘汰—结算」的视角分别落到单调栈和单调队列。前者处理最近边界、贡献区间与地形围水；后者处理滑动窗口最值及一类固定宽度 DP。重点不在背诵模板，而在明确：栈中存什么不变量、弹出时结算什么、等号交给哪一侧，以及窗口中先后顺序为何不能交换。

一、从候选下标出发

设数组为 a[0..n-1]。以「每个位置右边第一个严格更大元素」为例，扫描到 i 时，左侧一些位置仍没有答案。把这些位置放入栈中不是因为它们天然构成栈，而是因为它们都是尚未被右侧元素击败的候选。

若栈从底到顶对应的值单调递减，读到 a[i] 后，只要栈顶值小于 a[i]，就说明这个栈顶下标 j 的第一个更大元素正是 i：

j 一直留在栈中，说明从 j+1 到 i-1 没有值大于 a[j]；
当前 a[i] > a[j]，因此 i 满足「更大」；
扫描按下标递增，故 i 是最近的那个。

弹出不是丢弃信息，而是结算答案。弹完后把 i 入栈，恢复「从底到顶非增」这一不变量。栈保存下标而非数值：同一个值可能在不同位置拥有不同边界，后续还要计算距离、宽度、窗口是否过期；仅存值会丢掉这些信息。

新元素抵达时，栈顶中被击败的候选依次结算；未被击败的下标继续作为候选

1.1 摊还分析：为什么嵌套 `while` 仍是 $O(n)$

代码常有一个 for 套一个 while，但复杂度并非 $O(n^2)$ 。每个下标只会经历两次状态变化：第一次入栈，之后最多一次从栈顶弹出。把一次入栈和一次出栈各记为一个单位操作，全部下标合计最多 $2n$ 次栈操作，比较次数也与之同阶。因此总时间为 $O(n)$ ，额外空间为 $O(n)$ 。

更形式化地说，令势能 $\Phi$ 为当前栈大小。一次入栈的实际代价为 1，势能增加 1；一次出栈实际代价为 1，势能减少 1。虽然一次扫描可能连续弹出很多元素，但这些弹出消耗的是过去入栈积累的势能。总摊还代价不超过线性。单调队列同理：每个下标至多从队首过期删除一次，或从队尾因劣势删除一次，不会反复回到队列。

1.2 四个问题决定方向

写代码前，把题意翻译成四句话：

问题	决定的内容
要找什么关系？	更大、较大、更小、较小，决定弹栈条件。
答案在左还是右？	左侧答案通常在入栈前结算；右侧答案在扫描新元素时结算。
相等值归谁？	严格/非严格不等号决定重复元素的唯一归属。
结算后还要保留什么？	边界题保留最近挡板；贡献题保留距离；窗口题还要检查时效。

「单调递增栈」和「单调递减栈」容易因描述方向而混淆。下面约定都以栈底到栈顶的值描述：递减栈用于寻找更大元素，递增栈用于寻找更小元素。真正应记住的是弹栈谓词，而不是名称。

二、最近更大元素：把答案写在弹栈时

2.1 LeetCode 739：每日温度

题目要求每一天等待几天才遇到更高温。答案天然是「右侧第一个严格更大元素的下标差」。维护温度非增的下标栈：读到更高温 temperatures[i] 时，所有更低温的栈顶都在这一刻得到答案。

#include <stack>
#include <vector>

std::vector<int> dailyTemperatures(
    const std::vector<int>& temperatures) {
  const int n = static_cast<int>(temperatures.size());
  std::vector<int> answer(n, 0);
  std::stack<int> candidates;

  for (int i = 0; i < n; ++i) {
    while (!candidates.empty() &&
           temperatures[candidates.top()] < temperatures[i]) {
      const int day = candidates.top();
      candidates.pop();
      answer[day] = i - day;
    }
    candidates.push(i);
  }
  return answer;
}

循环不变量是：candidates 的下标递增，且对应温度从栈底到栈顶非增；其中每个下标的右侧严格更高温尚未出现。用 < 而非 <=，所以温度相同的旧下标不会被当前温度结算。它仍应等待未来真正更高的一天；最终留在栈中的位置答案保持初始值 0。

一个常见误解是「既然只要右边更高，为何不直接存温度？」答案是距离需要 i - day，而且两个相同温度日的等待时间可能不同。下标是候选的身份，值只是用来比较的属性。

2.2 LeetCode 496：下一个更大元素 I

496 的查询数组是 nums1，而所有边界关系定义在 nums2。应先在线性时间中预处理 nums2 的值到下一个更大值，再回答查询；不能为 nums1 的每个元素重新扫描 nums2。

#include <stack>
#include <unordered_map>
#include <vector>

std::vector<int> nextGreaterElement(
    const std::vector<int>& nums1,
    const std::vector<int>& nums2) {
  std::unordered_map<int, int> next;
  std::stack<int> candidates;

  for (const int value : nums2) {
    while (!candidates.empty() && candidates.top() < value) {
      next[candidates.top()] = value;
      candidates.pop();
    }
    candidates.push(value);
  }

  std::vector<int> answer;
  answer.reserve(nums1.size());
  for (const int value : nums1) {
    const auto it = next.find(value);
    answer.push_back(it == next.end() ? -1 : it->second);
  }
  return answer;
}

2.3 一个可复用的右侧边界模板

若要右侧第一个满足 a[right] > a[left] 的位置，答案以「被当前元素击败的历史候选」结算：

#include <stack>
#include <vector>

std::vector<int> nextStrictlyGreaterIndex(
    const std::vector<int>& values) {
  const int n = static_cast<int>(values.size());
  std::vector<int> right(n, n);
  std::stack<int> decreasing;

  for (int i = 0; i < n; ++i) {
    while (!decreasing.empty() &&
           values[decreasing.top()] < values[i]) {
      right[decreasing.top()] = i;
      decreasing.pop();
    }
    decreasing.push(i);
  }
  return right;
}

用 n 表示「不存在右边界」很实用：后续距离统一写成 right[i] - i，无需额外分支。若要右侧第一个严格更小元素，只需维护递增栈，并把弹栈条件改为 values[top] > values[i]。

三、等号不是细节：重复元素的归属协议

单调结构最隐蔽的 bug 往往不在方向，而在等号。对于互异数组，< 与 <= 的差别不显眼；有重复值时，它决定了相等元素谁留下、谁被结算，也决定贡献法会不会重复计数或漏计。

3.1 四种最近边界的含义

以找右边界为例：

弹栈条件	栈维持的关系	弹出元素得到的右侧位置
`a[top] < a[i]`	非增	第一个严格更大 `>`
`a[top] <= a[i]`	严格递减	第一个大于等于 `>=`
`a[top] > a[i]`	非减	第一个严格更小 `<`
`a[top] >= a[i]`	严格递增	第一个小于等于 `<=`

记忆方法不是机械背表：当前 i 弹掉栈顶，说明当前值就是栈顶的那个边界；弹栈谓词写的正是两者之间要满足的严格性。

3.2 同值元素必须选一侧承担责任

考虑 a = [3, 3]，若问题是每个元素作为子数组最小值的贡献。子数组 [0, 1] 的最小值等于 3，但它只能归属给下标 0 或下标 1，不能两者都算，也不能谁都不算。正确做法是让一侧采用严格比较、另一侧采用非严格比较：

左严格更小、右小于等于：相等值的区间归给左侧较早的位置；
左小于等于、右严格更小：相等值的区间归给右侧较晚的位置。

两种协议都正确，但必须成对出现。左右都严格，会让相同元素都把跨越对方的区间算进去；左右都非严格，则可能都被挡在对方外面，造成漏算。算法题中的「严格」并非文字修饰，而是计数空间的分割规则。

3.3 左边界可以在入栈前获得

右边界常在当前元素到来时让历史元素弹出。左边界则常在当前元素入栈前由栈顶给出：先持续弹掉不能成为左边界的元素，弹完后的栈顶就是最近仍满足关系的位置。以下函数求每个位置左侧第一个严格更小的下标；-1 表示不存在。

#include <stack>
#include <vector>

std::vector<int> previousStrictlySmallerIndex(
    const std::vector<int>& values) {
  const int n = static_cast<int>(values.size());
  std::vector<int> left(n, -1);
  std::stack<int> increasing;

  for (int i = 0; i < n; ++i) {
    while (!increasing.empty() &&
           values[increasing.top()] >= values[i]) {
      increasing.pop();
    }
    if (!increasing.empty()) {
      left[i] = increasing.top();
    }
    increasing.push(i);
  }
  return left;
}

注意这里弹出 >=，所以栈顶若存在就严格小于当前值。若题目需要左侧第一个小于等于，则应改为只弹出 >。不要只改注释或变量名，边界含义要从不等号推导出来。

四、直方图最大矩形：哨兵强制最后结算

LeetCode 84 给定柱高数组，要求最大矩形面积。固定某根柱 i 作为矩形最矮高度 h[i] 时，可扩展范围一直向左右延伸，直到遇到第一个严格更小柱。若左侧最近严格更小是 L，右侧最近严格更小是 R，那么以 h[i] 为短板的最大宽度为

$W_i = R - L - 1, \qquad A_i = h_i(R-L-1).$

直接为每根柱寻找两边界已经可做；更紧凑的单栈写法是在扫描到右边界时直接计算面积。栈维护非减高度下标。当前高度小于栈顶时，栈顶柱的右边第一个严格更小位置就是当前 i；弹出后新的栈顶是它左边最近小于等于的位置。为何左边不是严格更小也正确？同高柱的最大矩形会由其中一个代表计算到，非严格边界不会漏掉最大面积。

#include <algorithm>
#include <stack>
#include <vector>

int largestRectangleArea(const std::vector<int>& heights) {
  const int n = static_cast<int>(heights.size());
  std::stack<int> increasing;
  long long best = 0;

  for (int i = 0; i <= n; ++i) {
    const int current = i == n ? 0 : heights[i];
    while (!increasing.empty() &&
           heights[increasing.top()] > current) {
      const int mid = increasing.top();
      increasing.pop();
      const int left = increasing.empty() ? -1 : increasing.top();
      const long long width = i - left - 1;
      const long long area =
          static_cast<long long>(heights[mid]) * width;
      best = std::max(best, area);
    }
    increasing.push(i);
  }
  return static_cast<int>(best);
}

i == n 时虚拟读到高度 0 的右哨兵，它比所有非负柱高都小，于是让未结算柱依次弹出。代码没有真的复制数组，也没有访问 heights[n]；current 在条件表达式中安全产生。若允许柱高为负，0 就不再是可靠哨兵，需改用小于所有可能高度的值或在循环结束后手动清栈。题目通常保证柱高非负。

递增栈记录仍可向右延伸的柱；下降柱到来时，弹出柱的左右边界同时确定

4.1 用「结算时刻」理解宽度

当 mid 被 i 弹出时：

i 是 mid 右侧第一个高度严格小于 heights[mid] 的位置；
弹出 mid 后的栈顶 left 是左边最近高度小于等于它的位置；
因而 [left + 1, i - 1] 中每根柱都至少有 heights[mid] 高，宽度正好为 i - left - 1。

这也是为何必须在 pop() 后再读 left：弹出前的栈顶是自己，不是左挡板。increasing.empty() 时令 left = -1，把左边界统一成数组外的虚拟位置，消除了「从第 0 根柱开始」的特殊分支。

4.2 两趟边界法与一趟弹栈法如何选

两趟法显式计算 left[i]、right[i]，调试时易于打印和核验，适合题目还要求输出最大区间；一趟法空间常数更小、结构更贴近「右边界到达即结算」。二者本质相同：都用单调性让每个柱仅在其边界确定时被处理一次。不要为了「一趟」牺牲可读性；若需要复用左右边界，显式数组反而更合适。

五、子数组最小值之和：贡献法的边界分配

LeetCode 907 要计算所有非空子数组的最小值之和。枚举子数组有 $O(n^2)$ 个，逐个求最小值更慢。换一个枚举对象：固定 arr[i]，数一数有多少子数组把它作为依据协议选出的最小值。

本节固定采用：

L 是 i 左边最近的严格更小元素位置；
R 是 i 右边最近的小于等于元素位置。

那么左端点可从 L+1 到 i，共有 $i-L$ 种；右端点可从 i 到 R-1，共有 $R-i$ 种。arr[i] 的贡献为

$\operatorname{contrib}(i)=arr_i\,(i-L)\,(R-i).$

总和即所有贡献相加并取模。这一对边界把相等最小值的共同子数组归给更靠左的元素：右侧等值会阻挡左元素，左侧等值不会阻挡当前元素。每个子数组因此恰有一个责任下标。

#include <stack>
#include <vector>

int sumSubarrayMins(const std::vector<int>& arr) {
  constexpr long long kMod = 1'000'000'007LL;
  const int n = static_cast<int>(arr.size());
  std::vector<int> left(n, -1);
  std::vector<int> right(n, n);
  std::stack<int> indices;

  for (int i = 0; i < n; ++i) {
    while (!indices.empty() && arr[indices.top()] >= arr[i]) {
      indices.pop();
    }
    if (!indices.empty()) {
      left[i] = indices.top();
    }
    indices.push(i);
  }

  while (!indices.empty()) {
    indices.pop();
  }
  for (int i = n - 1; i >= 0; --i) {
    while (!indices.empty() && arr[indices.top()] > arr[i]) {
      indices.pop();
    }
    if (!indices.empty()) {
      right[i] = indices.top();
    }
    indices.push(i);
  }

  long long answer = 0;
  for (int i = 0; i < n; ++i) {
    const long long count =
        static_cast<long long>(i - left[i]) * (right[i] - i);
    answer = (answer + arr[i] * count) % kMod;
  }
  return static_cast<int>(answer);
}

左向扫描中弹出 >=，留下的栈顶严格更小；右向扫描中弹出 >，留下的栈顶小于等于。方向不同但目标一致，切勿把两个循环的符号写成一样。乘法前转换为 long long，否则距离与高度的乘积可能先在 int 中溢出；模运算只修正结果，无法挽回已经发生的整型溢出。

5.1 以 `[3, 3, 1]` 检验协议

对两个值为 3 的位置，左侧第一个 3 的右边界是第二个 3（因为右侧找 <=），它不能负责跨越下标 1 的子数组；第二个 3 的左边界是 -1（因为左侧只找 <，相等 3 被弹掉），因此 [0,1] 由第二个 3 负责。换用另一对协议时责任会反向，但总数不变。用这种短重复样例手算，比随机大数组更容易暴露等号错误。

5.2 贡献法的适用边界

贡献法适用于「总答案可以拆成每个位置独立贡献之和」，并且某位置的有效区间能由最近破坏条件的边界刻画。子数组最小值、最大值、某元素作为唯一最小/最大值的区间计数都符合。若子数组的评价依赖多个元素的复杂组合，或无法把区间资格分配给唯一责任元素，单调栈未必是合适工具。

六、接雨水：栈找到凹槽的封口

LeetCode 42 的水量由左右两边较低的墙决定。单调栈维护从底到顶非增的高度下标。当当前高度大于栈顶时，说明一个凹槽的右墙出现：先弹出谷底 bottom，再看弹出后的栈顶 left 是否存在；若存在，当前 i 是右墙，left 是左墙，能新增一层或多层水。

新增水的有效高度和宽度为

$H=\min(h_{left},h_i)-h_{bottom}, \qquad W=i-left-1, \qquad \Delta V=H\,W.$

#include <algorithm>
#include <stack>
#include <vector>

int trapRainWater(const std::vector<int>& height) {
  const int n = static_cast<int>(height.size());
  std::stack<int> decreasing;
  long long water = 0;

  for (int i = 0; i < n; ++i) {
    while (!decreasing.empty() &&
           height[decreasing.top()] < height[i]) {
      const int bottom = decreasing.top();
      decreasing.pop();
      if (decreasing.empty()) {
        break;
      }
      const int left = decreasing.top();
      const int boundedHeight =
          std::min(height[left], height[i]) - height[bottom];
      const int width = i - left - 1;
      water += static_cast<long long>(boundedHeight) * width;
    }
    decreasing.push(i);
  }
  return static_cast<int>(water);
}

这段代码中，bottom 不是整个盆地的唯一最低点，而是当前被右墙抬升、刚好可以结算的一层底部。连续弹栈会分别结算不同高度层，彼此不重叠。若弹出后栈空，当前元素左边没有围墙，不能蓄水，必须停止本轮；这正是 break 的语义。

6.1 与双指针解的取舍

本题也可用左右指针，详见双指针技术。双指针维护左右历史最高墙，较矮一侧的水位已被另一侧确定，空间 $O(1)$ ；单调栈空间 $O(n)$ ，但更直接表达「某个凹槽何时封口」，并可自然迁移到最近边界、直方图等题。

方法	时间	额外空间	核心状态	更适合
单调栈	$O(n)$	$O(n)$	尚未封口的递减墙	理解局部盆地与边界题迁移
双指针	$O(n)$	$O(1)$	两端最高墙与待定区间	只要求总水量、追求常数空间

不能把两种思路拼接为「栈顶加双指针」：它们各自的状态证明不同。选定一种后，围绕其不变量实现即可。

七、单调队列：有时效的最优候选

单调栈的候选只有被值关系击败才离开；滑动窗口中的候选还有第二种失效方式：它离开了窗口。单调队列通常用 std::deque<int> 存下标，队首到队尾按值单调，且下标递增。以窗口最大值为例，维护值非增队列：队首永远是当前窗口最大值，队尾则是新元素比较、淘汰劣势候选的位置。

LeetCode 239 的正确顺序必须明确：先清理过期下标，再维护队尾单调性，最后在窗口形成后读取队首。先处理时效，再处理价值；这样每个时刻的数据结构只保存当前窗口内尚可能成为最大值的下标。

#include <deque>
#include <vector>

std::vector<int> maxSlidingWindow(
    const std::vector<int>& nums,
    int k) {
  const int n = static_cast<int>(nums.size());
  std::vector<int> answer;
  if (k <= 0 || k > n) {
    return answer;
  }

  std::deque<int> decreasing;
  answer.reserve(n - k + 1);
  for (int i = 0; i < n; ++i) {
    while (!decreasing.empty() &&
           decreasing.front() <= i - k) {
      decreasing.pop_front();
    }
    while (!decreasing.empty() &&
           nums[decreasing.back()] <= nums[i]) {
      decreasing.pop_back();
    }
    decreasing.push_back(i);
    if (i >= k - 1) {
      answer.push_back(nums[decreasing.front()]);
    }
  }
  return answer;
}

此处队尾使用 <=，相等值时保留较新的下标。它至少和旧元素一样好，却过期得更晚，因此旧下标被支配，可以删除。若改为 <，保留较旧同值也仍能得到正确窗口最大值，只是候选更多；两种写法都可行，但必须理解保留策略。队列的值从队首到队尾非增，且所有下标都属于当前窗口；因此队首既不可能过期，也没有任何更大的候选，正是答案。

窗口右移时，队首先删除过期下标；新值再从队尾淘汰不可能胜出的较小候选

7.1 为什么队尾可以删除较小值

若已有下标 j < i 且 nums[j] <= nums[i]，从当前时刻起，只要 j 仍在任何未来窗口中，i 也在该窗口中（i 更晚过期），且 i 的值不小于 j。j 不会再成为最大值，故可以永久从队尾删除。这是单调队列的支配关系：新候选在数值上不差、在时间上更久，完全支配旧候选。

只从队尾删很关键。队首是目前最优且最早进入窗口的候选，只有它过期时才可从队首删；中间元素虽然暂时不是最大值，仍可能在更大元素过期后成为答案，不能随意删除。

7.2 最小值、最大值与初始化

窗口最小值只需反向：队首到队尾维护非减值，队尾删除 nums[back] >= nums[i]。以下是可独立使用的最小值版本，便于观察真正变化的只有比较符号。

#include <deque>
#include <vector>

std::vector<int> minSlidingWindow(
    const std::vector<int>& nums,
    int k) {
  const int n = static_cast<int>(nums.size());
  std::vector<int> answer;
  if (k <= 0 || k > n) {
    return answer;
  }

  std::deque<int> increasing;
  answer.reserve(n - k + 1);
  for (int i = 0; i < n; ++i) {
    while (!increasing.empty() &&
           increasing.front() <= i - k) {
      increasing.pop_front();
    }
    while (!increasing.empty() &&
           nums[increasing.back()] >= nums[i]) {
      increasing.pop_back();
    }
    increasing.push_back(i);
    if (i >= k - 1) {
      answer.push_back(nums[increasing.front()]);
    }
  }
  return answer;
}

当 k == 1，每个元素都应立即成为自己的窗口答案；当 k == n，只输出一个全局最值。k <= 0 和 k > n 不属于 LeetCode 239 的合法输入约束，但通用函数明确返回空结果，避免 reserve(n-k+1) 等表达式在非法参数下产生错误的容量转换。

八、固定宽度窗口 DP：队列维护转移最优值

单调队列不只用于数组窗口。若 DP 形如

$dp[i] = f(i) + \max_{j\in[i-k,\,i-1]} g(j),$

并且候选 g(j) 的相对比较不随 i 改变，那么可在扫描 i 时维护过去 $k$ 个 g(j) 的单调队列，队首就是转移最优值。最重要的前提有三个：

候选区间是固定宽度的滑动窗口，即下标只会按时间过期；
比较键与当前 i 无关，或可预先化为只依赖 j 的值 g(j)；
状态按下标顺序可得，新 dp[i] 只依赖已完成的先前状态。

这与一般的 DP 状态压缩、转移定义和边界初始化一脉相承，可结合动态规划阅读。这里不讨论斜率优化：后者维护的是随查询点变化的直线最优值，几何不变量和适用条件都不同，不能因为都用 deque 就混为一谈。

以下示例计算「从位置 0 出发，每次可前进 1 到 k 步，落在 i 得到 score[i]，求到达每个位置的最高得分」。转移为 dp[i] = score[i] + max(dp[j])，其中 j 在 [i-k, i-1]。这正是固定窗口最大值。

#include <deque>
#include <vector>

long long maxScoreWithJumps(
    const std::vector<int>& score,
    int k) {
  const int n = static_cast<int>(score.size());
  if (n == 0 || k <= 0) {
    return 0;
  }

  std::vector<long long> dp(n);
  std::deque<int> decreasing;
  dp[0] = score[0];
  decreasing.push_back(0);

  for (int i = 1; i < n; ++i) {
    while (!decreasing.empty() &&
           decreasing.front() < i - k) {
      decreasing.pop_front();
    }
    dp[i] = dp[decreasing.front()] + score[i];
    while (!decreasing.empty() &&
           dp[decreasing.back()] <= dp[i]) {
      decreasing.pop_back();
    }
    decreasing.push_back(i);
  }
  return dp.back();
}

这段顺序与滑动窗口题略有不同：在计算 dp[i] 前，队列中只应有先前状态，因此先删掉 j < i-k 的过期下标，立即读取队首；算出 dp[i] 后再用它维护队尾并入队。若把 i 先入队，就可能让状态引用自己，破坏转移的时间方向。若分数与路径长度相加可能超出 int，dp 必须使用 long long。

8.1 能优化与不能优化的转移

下表用于快速判断：

转移形式	单调队列可用？	原因
$dp[i]=a_i+\max_{j\in[i-k,i-1]}dp[j]$	可以	键为 `dp[j]`，窗口固定且比较不随 `i` 变。
$dp[i]=a_i+\min_{j\in[i-k,i-1]}dp[j]$	可以	改为维护递增队列。
$dp[i]=\max_{j\in[i-k,i-1]}(dp[j]+b_j)$	可以	键预处理为 `dp[j]+b[j]`。
$dp[i]=\max_j(dp[j]+i\cdot j)$	通常不可以	候选优劣会随 `i` 改变，不是固定比较键。
窗口长度随状态任意扩缩	不一定	需先证明过期顺序仍是单调的。

「单调队列优化 DP」不是见到 max 就套模板。必须先把转移改写为窗口内某个静态候选键的最值；如果比较结果会因当前状态改变，队尾删除就不再安全。

九、从模板到证明：每一次删除都要有理由

单调结构的正确性通常不靠「样例跑通」，而靠三类断言同时成立：

表示性：结构里保存了所有尚可能影响未来答案的候选；
安全删除：每次从栈或队列删除一个下标，都能说明它已结算、过期，或被另一个候选完全支配；
答案可读：在需要输出或计算时，结构给出的边界、队首或弹出元素确实对应题意。

这三个断言分别对应不漏、不错和能算出答案。把它们写清楚，换符号、改方向或迁移到新题时才不会依赖模糊直觉。

9.1 单调栈的删除证明

仍以右侧第一个严格更大元素为例。扫描到 i 前，递减栈中的任意 j 都满足两件事：j < i，且在半开区间 (j, i) 内没有大于 a[j] 的值。因为若存在，j 在那一刻已经被弹出。当前若 a[j] < a[i]，那么 i 是第一个严格更大元素；弹出 j 是结算，不是剪枝。

当前若 a[j] >= a[i]，j 留下也不是侥幸。a[i] 无法成为 j 的严格更大右边界；而 j 比 i 更早出现，未来若有值能击败 j，也会顺带击败或越过 i，二者的相对顺序仍可由栈维护。把 i 压在 j 之上，恰好保留了所有尚未确定右边界的、从下到上非增的候选链。

这段论证还解释了一个常见调试原则：若你无法用一句「为什么删掉它后永远不需要它」说明某次 pop，就不该写这次 pop。例如最近边界题中从栈顶删除，是因为当前元素已使其答案确定；窗口最大值从队尾删除，是因为新元素同时数值不小、生命周期更长；这两种删除理由不同，不能混用。

9.2 单调队列的删除证明

固定窗口最大值中，队列保存的是当前窗口内一组下标 q_0 < q_1 < \cdots < q_m，且

$a_{q_0} > a_{q_1} > \cdots > a_{q_m}$

（使用 <= 弹队尾时为严格递减；保留相等值时为非增）。队首过期的判据只取决于下标：在处理 i 时，窗口左端是 i-k+1，故 q_0 <= i-k 等价于 q_0 已不在窗口内。这个检查放在队尾维护之前，意味着后续每个候选都满足时间有效性。

队尾删除则利用支配：若 q_m < i 且 a[q_m] <= a[i]，所有包含 q_m 的未来窗口只要仍包含它，也必包含更晚的 i；i 的值不小，过期不早。q_m 不可能再成为最大值。注意此证明依赖窗口左端只向右移动、窗口宽度固定；若窗口可以向左扩张，已删掉的旧元素可能重新有效，普通单调队列就不适用。

9.3 用反例验证顺序

窗口最大值的三步不是风格问题。以 nums = [9, 1, 2]、k = 2 为例，处理 i = 2 时合法窗口是 [1, 2]。若没有先执行过期检查，队首还可能是下标 0、值 9，读取后会错误输出 9。正确流程先删除 0 <= 2 - 2，再比较队尾的值 1 与新值 2，最后读取队首 2。

同样，直方图中若没有右哨兵，递增数组 [1, 2, 3] 的任一柱都不会在主循环中被弹出，面积从未结算；若读左边界时忘了先弹出中柱，栈顶会仍是中柱自身，宽度少算一格。边界错误不应只用「加一个 if」掩盖，应回到结算时刻重新定义左右挡板。

十、常见变体：改变边界，不改变候选思想

10.1 环形数组的下一个更大元素

LeetCode 503 把数组看成环，最后一个元素之后可以回到第一个元素。暴力做法会从每个位置绕一圈。单调栈仍然有效：逻辑上扫描 2n 个位置，用 i % n 映射回原数组；只在第一轮把下标压栈，第二轮仅负责用开头元素结算仍未完成的候选。

#include <stack>
#include <vector>

std::vector<int> nextGreaterElementsCircular(
    const std::vector<int>& nums) {
  const int n = static_cast<int>(nums.size());
  std::vector<int> answer(n, -1);
  std::stack<int> decreasing;

  for (int i = 0; i < 2 * n; ++i) {
    const int index = i % n;
    while (!decreasing.empty() &&
           nums[decreasing.top()] < nums[index]) {
      answer[decreasing.top()] = nums[index];
      decreasing.pop();
    }
    if (i < n) {
      decreasing.push(index);
    }
  }
  return answer;
}

n == 0 时循环条件一开始为假，因此 i % n 不会执行，函数安全返回空数组。第二轮绝不能再次入栈，否则同一身份会重复进入候选集，摊还分析和「第一个更大」的语义都会被破坏。扫描两轮仍是 $O(n)$ ：第二轮没有新增下标，每个原下标最多被弹出一次。

环形题的关键不是「把数组复制一遍」，而是明确候选的可见范围从右侧线段延长到至多一个完整环。若题目允许绕多圈才算答案，或答案依赖经过次数，则这份模板的语义不再成立。

10.2 绝对值差与子数组范围和

LeetCode 2104 的子数组范围是 max - min。所有子数组范围之和可以拆为「所有子数组最大值之和」减去「所有子数组最小值之和」。这正是贡献法的加性优势：同一子数组的两个统计量可分别唯一归属，再在线性外层相减。数组可含负数，因此尾部清算必须使用控制流哨兵，不能把数值 0 当成虚拟元素；后者会错误改变负数的边界。

#include <stack>
#include <vector>

long long sumSubarrayRangesAnyInt(
    const std::vector<int>& nums) {
  const int n = static_cast<int>(nums.size());
  long long total = 0;
  std::stack<int> increasing;
  std::stack<int> decreasing;

  for (int i = 0; i <= n; ++i) {
    while (!increasing.empty() &&
           (i == n || nums[increasing.top()] > nums[i])) {
      const int mid = increasing.top();
      increasing.pop();
      const int left = increasing.empty() ? -1 : increasing.top();
      total -= static_cast<long long>(nums[mid]) *
          (mid - left) * (i - mid);
    }
    while (!decreasing.empty() &&
           (i == n || nums[decreasing.top()] < nums[i])) {
      const int mid = decreasing.top();
      decreasing.pop();
      const int left = decreasing.empty() ? -1 : decreasing.top();
      total += static_cast<long long>(nums[mid]) *
          (mid - left) * (i - mid);
    }
    if (i < n) {
      increasing.push(i);
      decreasing.push(i);
    }
  }
  return total;
}

这里的短路逻辑很重要：当 i == n 时，|| 的右侧不会求值，因此不会访问 nums[n]；两栈都被无条件清空。严格符号令重复最大/最小值由某一侧代表，不影响总和。这个例子也展示了如何审查示例代码：不仅看典型输入是否正确，还要检查哨兵值是否覆盖题目允许的整个值域。

10.3 可见人数与「遮挡」关系

有些题目不要求第一个更大元素，而问右侧能看见多少人、能保留哪些轮廓。此时单调栈仍按候选淘汰工作，但被弹出的元素不一定只有一个最终答案；它也可能在被弹出前对当前元素贡献一次可见计数。关键是先把「中间元素何时遮挡」翻译成严格关系，再决定栈中保留递增还是递减轮廓。

例如从右向左扫描，每个新身高 h 依次弹出不高于它的栈顶：这些人对当前人可见；弹完若栈还非空，那个更高的人也可见但挡住了更远者。这里 <= 的等号含义是：相同高度中，靠近当前人的一个已经足以遮挡更远的同高者。与每日温度的 < 不同，因为两个题的「相等」语义不同，不该只因都叫「更大」就复用符号。

10.4 何时不该使用单调栈

最近边界并不自动意味着单调栈。若数组允许动态修改，而每次查询都要问某位置的下一个更大元素，静态一次扫描无法维护更新后的关系；应根据操作选择线段树、平衡树或离线重建。若题目询问任意区间的最大值，且查询不按窗口连续滑动，稀疏表、线段树或前缀结构可能更合适。

另一个反例是「左、右边界之间还必须满足和、颜色、频次等额外条件」。单调栈可以给出候选边界，但未必能独立解决附加约束。先确认问题的核心瓶颈确实是最近比较关系，避免把结构当成万能装饰。

十一、手工推演：把不变量落在纸上

学习单调结构时，最有效的练习不是默写模板，而是画出每次迭代后的结构。以下对 values = [2, 1, 4, 3, 5] 求右侧第一个严格更大位置，维护递减栈：

扫描到 `i`	当前值	弹出并结算	扫描后栈（底→顶）
0	2	无	`0:2`
1	1	无	`0:2, 1:1`
2	4	`1 → 2`，`0 → 2`	`2:4`
3	3	无	`2:4, 3:3`
4	5	`3 → 4`，`2 → 4`	`4:5`

表中「1 → 2」表示下标 1 的右侧第一个更大位置是 2。任何时刻，栈里从底到顶的值非增，且它们的答案尚未出现。对于全递增数组，每一步都会清空此前栈；对于全递减数组，栈持续增长并在结尾保留所有未解候选；这两种极端正好检验摊还 $O(n)$ 与尾部默认值。

窗口最大值可用 nums = [1, 3, 1, 2, 0, 5]、k = 3 推演。处理 i = 3 前，队列为 [1:3, 2:1]；i-k=0，队首 1 未过期；新值 2 使队尾 2:1 出队，队列变为 [1:3]，再放入 3:2。窗口 [1,3] 的答案为 3。到 i = 4 时，队首 1 仍有效，0 无法支配 2；到 i = 5 时，先删去下标 1（它过期），随后 5 从队尾清空 0 和 2，答案变为 5。每一步都能明确说明候选为何离开。

11.1 一份考场检查顺序

在写完单调栈或队列后，可按下面顺序静态检查，不需要凭随机数据祈祷：

写出结构中下标的值关系：从底到顶/首到尾到底是严格还是非严格；
写出元素离开结构的每一种原因：结算、过期、被支配是否全部覆盖；
给空结构指定边界：-1、n、默认答案或停止条件；
对 [x, x] 检查等号归属，对递增和递减数组检查哨兵；
对 k=1 与 k=n 检查窗口左端与答案生成时机；
对最大高度、最大长度检查所有乘法和累加是否先提升到宽类型。

这份清单的价值在于把「边界感觉」转成可重复执行的证明步骤。尤其是第 2 项：若一个下标离开时既没有得到最终答案、也没有过期、更没有被未来候选完全支配，删除就必然有漏洞。

十二、边界协议速查：先定义答案，再选择符号

单调栈题最容易出现的错误是从某份模板开始改，而不是从答案定义开始推。更稳妥的顺序是先写下目标边界的数学谓词，再反推栈顶为何必须被弹出。以下表格以「当前扫描到 i，栈顶为 top」为统一场景。

目标	栈的值关系（底→顶）	当前应弹出 `top` 的条件	被弹出者得到的关系
右侧第一个 `>`	非增	`a[top] < a[i]`	`i` 是 `top` 的右侧严格更大
右侧第一个 `>=`	严格递减	`a[top] <= a[i]`	`i` 是 `top` 的右侧大于等于
右侧第一个 `<`	非减	`a[top] > a[i]`	`i` 是 `top` 的右侧严格更小
右侧第一个 `<=`	严格递增	`a[top] >= a[i]`	`i` 是 `top` 的右侧小于等于

「栈的关系」不是额外选择，而是弹栈循环结束后的必然结果。例如要找右侧严格更小，循环删除所有高度大于当前高度的候选，所以压入当前元素后，栈从底到顶只能是非减。若某篇题解把它叫作「递增栈」，应追问它是否允许相等；名称没有 <、<= 精确。

12.1 左右边界如何成对选择

贡献题可以把左右边界看成一扇门：左门决定左端点能跨过哪些同值，右门决定右端点能跨过哪些同值。下面两组协议都是完整、互斥且覆盖全部子数组的划分。

责任归属	左边界	右边界	同值子数组归给
最左代表	最近 `<`	最近 `<=`	最靠左的等值最小/最大元素
最右代表	最近 `<=`	最近 `<`	最靠右的等值最小/最大元素

对于最小值，第一组可用「左向弹 >=、右向弹 >」实现；第二组符号对调。对于最大值，则把「小」替换为「大」，同样保持一严一非严。选择哪一组通常无关紧要，但实现中必须从左到右一致地坚持一个协议。

以 arr = [2, 2, 2] 为例，总共有 6 个非空子数组。采用最左代表协议时，长度为 2 的 [0,1] 和 [1,2] 分别归属下标 0、1，长度为 3 的 [0,2] 归属下标 0；采用最右代表协议时，它们分别归属下标 1、2、2。贡献的分配不同，求和完全相同。若你算出的总负责次数不是 6，应优先检查等号而非乘法。

12.2 线性栈与显式边界数组

单栈一趟结算最适合只要聚合值的题：直方图面积、围水总量、某种总贡献。因为右边界到来时，mid、left、right 同时可得，结果能立即累加，额外数组无须存在。

若题目要求输出每个位置的左/右边界、复原区间、对多个后续公式复用边界，显式数组更清晰。下例为任意整数数组计算左右第一个严格更小位置；尾部通过第二次扫描自然得到，不需要虚拟数值哨兵。

#include <stack>
#include <utility>
#include <vector>

std::pair<std::vector<int>, std::vector<int>>
strictlySmallerBoundaries(const std::vector<int>& values) {
  const int n = static_cast<int>(values.size());
  std::vector<int> left(n, -1);
  std::vector<int> right(n, n);
  std::stack<int> indices;

  for (int i = 0; i < n; ++i) {
    while (!indices.empty() &&
           values[indices.top()] >= values[i]) {
      indices.pop();
    }
    if (!indices.empty()) {
      left[i] = indices.top();
    }
    indices.push(i);
  }

  while (!indices.empty()) {
    indices.pop();
  }
  for (int i = n - 1; i >= 0; --i) {
    while (!indices.empty() &&
           values[indices.top()] >= values[i]) {
      indices.pop();
    }
    if (!indices.empty()) {
      right[i] = indices.top();
    }
    indices.push(i);
  }
  return {left, right};
}

这里左右均采用严格更小，适合「每个位置自己的最大可扩张区间」一类问题，但不适合直接拿来做含重复值的贡献求和：等值位置间的区间会重叠。数据结构负责找到你要求的边界，是否能直接用于计数仍取决于责任分配协议。

十三、实现层面的选择与成本

13.1 `std::stack`、`std::deque` 与 `std::vector`

std::stack<int> 清楚表达 LIFO 语义，适合文章和多数面试代码；其默认底层容器为 std::deque<int>。当性能敏感且只需栈操作时，也可用预留容量的 std::vector<int> 作为手写栈，减少分段容器的间接性。两者的算法不变量完全相同，差异只在接口和常数。

#include <vector>

std::vector<int> nextGreaterIndexWithVectorStack(
    const std::vector<int>& values) {
  const int n = static_cast<int>(values.size());
  std::vector<int> right(n, n);
  std::vector<int> stack;
  stack.reserve(values.size());

  for (int i = 0; i < n; ++i) {
    while (!stack.empty() &&
           values[stack.back()] < values[i]) {
      right[stack.back()] = i;
      stack.pop_back();
    }
    stack.push_back(i);
  }
  return right;
}

不要用 std::vector 模拟单调队列的队首删除：erase(begin()) 是线性移动，会把总复杂度破坏为 $O(n^2)$ 。窗口题必须使用 std::deque，或用数组加递增头尾指针实现真正的 $O(1)$ 两端操作。容器选择要服务于删除方向，而不是只看能否存下元素。

13.2 不复制数组的哨兵写法

直方图最常见的代码会构造 heights + [0]，可读性不错，但会额外复制一份数据。若输入规模大或函数接口承诺不分配，使用 i <= n 与条件表达式读取虚拟高度可避免复制。前文的 LeetCode 84 代码正是这种方式。

不过哨兵值必须小于会被结算的所有有效值。柱高非负时取 0 没问题；若是任意 int，不要试图取 INT_MIN - 1，这本身会溢出。可选择「循环到 n 时直接令弹栈条件成立」的控制流哨兵，或在遍历后另写一个 while 清栈。空间优化不能以边界安全为代价。

13.3 空间下界与在线性

单调栈的最坏空间确实是 $O(n)$ ：严格递减数组在寻找右侧更大元素时，直到扫描结束都无法结算任何候选；严格递增柱高在直方图中也会积累全部下标。这个空间不是实现不佳，而是在线扫描尚未见到右边界时必须保存的信息。

窗口队列的空间上界是 $O(k)$ ，而不是一般地写 $O(n)$ 。队列中下标都在当前宽度为 k 的窗口内，且每个下标不同。若 k 可接近 n，两种写法的渐近空间一致；若 k 很小，明确 $O(k)$ 能更准确描述算法利用了时效约束。

13.4 读题时的信号词

以下词汇经常提示单调结构，但它们只是入口，不是证明：

「下一个」「最近」「第一个」：优先考虑最近大/小边界；
「作为最小值/最大值的所有子数组」：尝试贡献法与等号协议；
「最大矩形」「可扩展到哪里」：寻找左右第一个破坏条件；
「连续窗口的最大/最小」：检查固定宽度与下标过期；
「至多相隔 k 步的最优转移」：尝试把 DP 改写成窗口最值。

反过来，看到「任意区间查询」「动态更新」「比较键随查询位置变化」时应先警惕。结构的名字不能替代适用条件；能否安全删除旧候选才是最终判据。

十四、复杂度、模板与排错清单

14.1 方法对照

场景	结构	维护不变量	单个下标离开原因	时间 / 空间
下一个更大/更小	单调栈	候选值单调，均未结算	被当前元素击败	$O(n)$ / $O(n)$
直方图最大矩形	递增栈	柱仍可向右延伸	首个更矮柱到来	$O(n)$ / $O(n)$
子数组最值之和	两次单调栈	边界协议唯一分配重复值	左右挡板确定	$O(n)$ / $O(n)$
接雨水	递减栈	未封口的左墙链	右墙使凹槽可结算	$O(n)$ / $O(n)$
固定窗口最值	单调队列	当前窗口候选按值单调	过期或被更优新项支配	$O(n)$ / $O(k)$
固定跨度 DP	单调队列	可转移状态的最优候选	超出跨度或被支配	$O(n)$ / $O(k)$

下面给出两个可直接改写的极简骨架。它们省略具体答案逻辑，但不省略最重要的不等号位置。

#include <stack>
#include <vector>

void resolveByNextGreater(const std::vector<int>& values) {
  std::stack<int> decreasing;
  for (int i = 0; i < static_cast<int>(values.size()); ++i) {
    while (!decreasing.empty() &&
           values[decreasing.top()] < values[i]) {
      const int resolved = decreasing.top();
      decreasing.pop();
      (void)resolved;
    }
    decreasing.push(i);
  }
}

#include <deque>
#include <vector>

void maintainWindowMaximum(
    const std::vector<int>& values,
    int k) {
  std::deque<int> decreasing;
  for (int i = 0; i < static_cast<int>(values.size()); ++i) {
    while (!decreasing.empty() &&
           decreasing.front() <= i - k) {
      decreasing.pop_front();
    }
    while (!decreasing.empty() &&
           values[decreasing.back()] <= values[i]) {
      decreasing.pop_back();
    }
    decreasing.push_back(i);
  }
}

14.2 高频陷阱清单

栈里只存值。 最近边界、宽度、距离和窗口时效都依赖位置；除非题目保证值唯一且不需要下标，否则存下标。
忘记哨兵或尾部清算。 直方图末尾仍在栈中的柱没有右边界；追加虚拟低柱，或显式清栈，二者必须有一个。
等号两边不配对。 贡献法必须一严格一非严格；先写出「相等区间归左还是归右」，再确定 > / >=。
把弹出前的栈顶当左边界。 直方图和围水中，pop() 后的新栈顶才是左挡板。
窗口读取过期队首。 每轮先删除 index <= i-k 的下标，再维护队尾；生成答案前队首必须仍在窗口内。
从队首删除被新元素支配的候选。 支配关系只比较新元素和队尾；队首只能因过期离开。
DP 入队时机错位。 若 dp[i] 依赖过去状态，先清理并查询、后计算、再入队；不要让 i 参与自己的转移。
把 while 当作二次复杂度。 分析下标的生命周期，不要只数循环嵌套；每个候选至多入、出一次。
面积或贡献在 int 中相乘。 先转为 long long，尤其是高度乘宽度、三项贡献和累加值。
名称掩盖不变量。 increasing、decreasing 只是提示；每次修改比较符号后，重新用「栈底到栈顶」写出值关系并手算重复样例。

小结

单调栈和单调队列的共同语言是候选管理：保存还没有被证明无用的下标，利用新元素一次淘汰被支配者，在淘汰时结算边界、面积、贡献或答案。栈没有时间上限，适合「第一个破坏单调性的位置」；队列有窗口时效，适合「当前有效候选的最值」。

面对新题，可按以下顺序判断：先问答案是否由最近更大/更小边界决定；再问某个元素能否把一批区间唯一归属给自己；若对象是滑动窗口或固定跨度 DP，再检查候选是否会按下标单调过期、其优劣是否由静态键决定。最后用重复值、全单调数组、窗口端点和空栈/空队列样例验证不变量。掌握这些问题，模板自然会从题意中长出来，而不是成为脆弱的记忆负担。