如何用栈在 JavaScript 中高效求解每个元素的下一个更大元素-js教程-PHP中文网

如何用栈在 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。

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

Java调试

通过 JDWP 实现 Java 远程调试：连接远程 JVM、设置断点、单步执行代码、查看变量值、获取调用栈。适用于需要调试远程 Java 应用、排查运行时状态、追踪代码执行流程的场景。术语注解 JDWP：Java Debug Wire Protocol，Java 调试有线协议（Java 远程调试底层通信协议） remote JVM：远程 Java 虚拟机 step through code：代码单步调试（步入 / 步过 / 步出调试） inspect variables：变量查看 / 变量检视 stac

下载

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]  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]

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