下一个更大元素

如何求每个元素右侧第一个更大元素？

• 通用做法 (739 每日温度): 遍历时维护单调递增栈 (存下标);
• 弹栈: 当前元素大于栈顶下标对应的元素时, 该下标就找到了答案, 记录距离 i - index;
• 收尾: 从未被弹出的下标没有更大元素, 保持初始值;
• 时间 $O(n)$, 空间 $O(n)$;

const dailyTemperatures = (temperatures) => {
  const res = new Array(temperatures.length).fill(0);
  const stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length && temperatures[i] > temperatures[stack.at(-1)]) {
      const index = stack.pop();
      res[index] = i - index;
    }
    stack.push(i);
  }
  return res;
};

子集查询如何复用一次遍历的结果？

• 场景 (496): nums1 是 nums2 的子集, 要对 nums1 每个元素给出它在 nums2 中的答案;
• 做法: 只对 nums2 跑一次单调栈, 弹栈时把 被弹出元素 → 当前元素 记入哈希表;
• 查询: nums1 的元素直接查表, 查不到即 -1;

const nextGreaterElement = (nums1, nums2) => {
  const map = {};
  const stack = [];
  for (const num of nums2) {
    while (stack.length && num > stack.at(-1)) {
      map[stack.pop()] = num;
    }
    stack.push(num);
  }
  return nums1.map((num) => map[num] ?? -1);
};

循环数组上如何求下一个更大元素？

• 场景 (503): 数组首尾相接, 每个元素还能看到它前面的元素;
• 做法: 把遍历范围扩到 2n, 用 i % n 映射回真实下标;
• 注意: 栈中存下标而非值, 避免重复元素互相干扰;

const nextGreaterElements = (nums) => {
  const n = nums.length;
  const res = new Array(n).fill(-1);
  const stack = [];
  for (let i = 0; i < 2 * n; i++) {
    while (stack.length && nums[i % n] > nums[stack.at(-1)]) {
      res[stack.pop()] = nums[i % n];
    }
    stack.push(i % n);
  }
  return res;
};