JavaScript栈方法求解每个元素的下一个更大元素

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

在算法面试或日常开发中，「下一个更大元素」（Next Greater Element, NGE）是个绕不开的经典问题。简单来说，就是给一个数组，要求你为每个元素找出它右边第一个比它大的数。如果找不到，就返回 -1。

最直接的思路当然是暴力破解：对每个元素，都向右扫描一遍。但这样一来，时间复杂度就飙升到了 O(n)，数据量稍大点，性能就吃不消了。有没有更聪明的办法？当然有，这就是今天要讲的「单调栈」解法，它能将复杂度降到 O(n)。

不过，很多人在实现时容易掉进坑里，比如遍历方向搞反、索引处理混乱。别急，我们一步步来拆解。

核心思路：为什么是单调栈，为什么从右往左？

这个解法的精髓在于两点：一是使用一个从栈底到栈顶严格递减的栈，二是采用从右向左的逆序遍历。

你可以把这个栈想象成一个“待命区”，里面存放的都是那些还没找到自己“下一个更大元素”的候选者。当我们从数组末尾开始向前遍历时，对于当前元素 arr[i]，逻辑就非常清晰了：

• 首先，把栈顶所有小于等于 arr[i] 的元素都弹出去。为什么？因为这些被弹出的元素，它们的值都不比 arr[i] 大，而且位置还在 arr[i] 的右边。对于 arr[i] 左边的元素来说，arr[i] 显然是比这些栈顶元素更近、更优的潜在“更大元素”候选。所以，它们没机会了，可以退场了。
• 清理完栈后，如果栈不空，那么栈顶元素就是 arr[i] 右边第一个比它大的数，直接赋值给结果数组。
• 如果栈空了，那就说明右边没有比它大的数，结果记为 -1。
• 最后，别忘了把当前的 arr[i] 压入栈中。因为它现在成了其左侧元素的潜在“下一个更大元素”候选者，需要进入“待命区”。

这个过程就像是在为每个元素寻找靠山，从右往左找，能确保我们总是用最新、最近的信息来更新状态。

一份可直接上手的健壮实现

理解了原理，代码实现就水到渠成了。下面这份 Ja vaScript 实现经过了多组测试用例的验证，逻辑清晰，可以直接拿去用。

function nextGreaterElement(arr) {
  if (arr.length === 0) return [];
  const n = arr.length;
  const result = new Array(n).fill(-1); // 默认-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];
    }
    // 当前元素入栈，成为左侧元素的候选
    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]

避开这些常见的坑

掌握了标准解法，我们再来看看哪些地方容易出错，理解了这些，你才算真正吃透了这个问题。

• 遍历方向是关键：最常见的误区就是试图从左向右遍历并同时维护单调栈。这会导致结果数组的索引对应关系极其混乱，因为你很难在正向扫描时确定一个元素最终会被谁“认领”。逆序遍历是保证逻辑清晰的不二法门。
• 栈里存什么？：上面的实现选择直接存储元素值，而不是索引。对于基础版的 NGE 问题，这完全够用，而且更简洁。如果存索引，在一些边界操作时（比如用 splice 或 unshift 调整结果顺序），反而可能引入不必要的复杂度或 O(n) 操作。
• “严格大于”的边界：注意代码中的比较条件是 <=。这意味着我们要弹出所有小于或等于当前值的栈顶元素，这样才能保证找到的是第一个严格更大的元素。如果把 <= 误写成 <，遇到相等值时逻辑就错了。
• 边界情况：空数组和单元素数组，上面的代码通过前置判断和默认填充 -1 的方式已经妥善处理了。

最后提一句，这个逆序单调栈的模板是解决一系列“下一个更大”类问题的基础。无论是 LeetCode 上经典的 496 题（Next Greater Element I），还是它的变体 503 题（循环数组的下一个更大元素），核心思想都是一脉相承的。把这个基础打牢了，再遇到更复杂的变化，你也能从容应对。