单调栈：把「下一个更大的数」从 O(n²) 拉回 O(n)

「对每个元素，找它右边第一个比它大的数」——暴力写法是两层循环。单调栈把它变成一次遍历，代价是承认栈里存的是还没找到答案的下标。

模板

从左往右扫，栈里保持一个递减序列；新元素来了，把比它小的都弹出去，那些被弹出去的元素的答案就是当前这个元素：

function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];
  for (let i = 0; i < nums.length; i += 1) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

关键在于 while 里弹出去的元素当场就拿到了答案，以后不会再被讨论。所以内层 while 虽然看着像嵌套循环，总执行次数却是 O(n)。

为什么是 O(n)

摊还分析很简单：每个下标在 for 里入栈一次，最多被 pop 一次。总操作数 ≤ 2n，与数据分布无关。这也是它比「每个元素向后扫描」强的唯一原因 —— 后者在最坏情况下（递减序列）每次要扫到底。

同一形状的四个问题

问题	栈里维护	弹出时机
下一个更大元素	递减	新元素更大
柱状图最大矩形	递增	新元素更矮
接雨水	递减（存高度）	新元素更高
每日温度	递减（存下标）	新温度更高

认出「找左/右第一个比自己大/小」就能套模板；接雨水的变形是弹出时顺手算一块水的面积。

两个容易写错的细节

• 栈里存下标而不是值：需要距离（每日温度问的是隔几天）或需要位置时，值不够用；存下标一定不会错。
• 相等时弹不弹：< 还是 <= 决定重复元素得到的是「严格更大」还是「大于等于」。这个选择会影响结果里同一值的位置，写之前先想清楚要哪个语义。

只要题目在问「左边/右边第一个比我大/小的东西」，就先想栈，别先想双层循环。