在JavaScript中用栈高效求解每个元素的下一个更大元素

本文详解使用单调栈（从右向左遍历）求解「下一个更大元素」问题的标准解法，修正常见索引错位与栈维护逻辑错误，并提供可直接运行的健壮实现。

本文详解使用单调栈（从右向左遍历）求解「下一个更大元素」问题的标准解法，修正常见索引错位与栈维护逻辑错误，并提供可直接运行的健壮实现。

「下一个更大元素」（Next Greater Element, NGE）是经典的栈应用问题：对数组中每个元素 arr[i]，找出其右侧第一个严格大于它的值；若不存在，则返回 -1。虽然直觉上可对每个元素向右线性扫描（O(n²)），但借助单调递减栈并逆序遍历，可在 O(n) 时间内高效解决。

关键在于理解栈的语义：我们维护一个从栈底到栈顶严格递减的栈，它保存的是「尚未找到 NGE 的候选元素」。当从右往左遍历（i = n-2 到 0）时，对于当前元素 arr[i]：

• 弹出所有 ≤ arr[i] 的栈顶元素（它们不可能成为左侧任何元素的 NGE，因为 arr[i] 更近且不更小）；
• 若栈为空 → 右侧无更大元素，result[i] = -1；
• 否则栈顶即为 arr[i] 的下一个更大元素；
• 最后将 arr[i] 压入栈，作为其左侧元素的潜在 NGE。

以下是符合标准、通过全部测试用例的实现：

function nextGreaterElement(arr) {  if (arr.length === 0) return [];  const n = arr.length;  const result = new Array(n).fill(-1);  const stack = []; // 存储元素值（非索引），维持单调递减  // 从右往左遍历  for (let i = n - 1; i >= 0; i--) {    // 弹出所有小于等于当前元素的值（破坏单调性的元素）    while (stack.length > 0 && stack[stack.length - 1] <= arr[i]) {      stack.pop();    }    // 若栈非空，栈顶即为下一个更大元素    if (stack.length > 0) {      result[i] = stack[stack.length - 1];    }    // 当前元素入栈，作为左侧元素的候选NGE    stack.push(arr[i]);  }  return result;}// 测试用例验证console.log(nextGreaterElement([56, 23, 1, 5, 18, 17])); // 输出: [-1, -1, 5, 18, -1, -1]console.log(nextGreaterElement([70, 60, 1, 4, 8, 12, 50, 23])); // 输出: [-1, -1, 4, 8, 12, 50, -1, -1]console.log(nextGreaterElement([1, 2, 3, 4, 5])); // 输出: [2, 3, 4, 5, -1]console.log(nextGreaterElement([5, 4, 3, 2, 1])); // 输出: [-1, -1, -1, -1, -1]

⚠️ 注意事项与常见误区：

立即学习“Java免费学习笔记（深入）”；

• 切勿正向遍历+简单压栈：原提问中正向逻辑混淆了“已处理”与“待处理”关系，导致索引错位（如 result.push() 顺序无法对应原始位置）；
• 栈中存值而非索引更简洁：本解法无需记录索引，避免 splice 或 unshift 等 O(n) 操作，时间复杂度严格 O(n)；
• 边界处理：空数组、单元素数组需单独考虑，但上述代码中 new Array(n).fill(-1) 已天然支持；
• 严格大于：比较时使用 <= 弹出，确保找到的是第一个严格更大的元素（而非大于等于）。

该解法是 LeetCode 第 496 题「Next Greater Element I」及变体的标准基础，掌握其逆序+单调栈思想，即可延伸解决循环数组 NGE（如第 503 题）或带索引映射的复杂场景。