这是 LeetCode 2454「下一个更大元素 IV」的 JavaScript 实现,核心思路是两次单调栈:

```javascript
var secondGreaterElement = function(nums) {
    const n = nums.length;
    const ans = new Array(n).fill(-1);
    // 第一个栈存待找第一个更大元素的下标
    const stack1 = [];
    // 第二个栈存待找第二个更大元素的下标
    const stack2 = [];

    for (let i = 0; i < n; i++) {
        // 当前元素作为 stack2 中某些索引的第二个更大元素
        while (stack2.length && nums[stack2[stack2.length - 1]] < nums[i]) {
            ans[stack2.pop()] = nums[i];
        }

        // 当前元素作为 stack1 中某些索引的第一个更大元素
        // 注意:需要借助临时栈保持顺序
        const temp = [];
        while (stack1.length && nums[stack1[stack1.length - 1]] < nums[i]) {
            temp.push(stack1.pop());
        }
        // 反转后加入 stack2(后遇到的下一个更大就是第二次出现)
        while (temp.length) {
            stack2.push(temp.pop());
        }

        stack1.push(i);
    }

    return ans;
};
```

思路说明

1. 问题转化
      每个元素要找到第二个比它大的元素,等价于先找第一个更大的,再找下一个更大的。
2. 双栈处理
   · stack1:等待找第一次更大元素的下标(单调递减栈)
   · stack2:已经找到第一次更大、正在等待第二次更大的下标
3. 遍历过程
   · 当遍历到 nums[i] 时,先检查它能否作为 stack2 中某些元素的第二次更大 → 弹出并记录答案
   · 再检查它能否作为 stack1 中某些元素的第一次更大 → 弹出并暂存到 stack2(因为已经找到了第一次更大,现在开始等第二次)
   · 最后将当前下标 i 压入 stack1,等待后续元素为它找第一次更大

复杂度

· 时间:O(n),每个元素最多入栈出栈两次
· 空间:O(n)

示例

```javascript
console.log(secondGreaterElement([2,4,0,9,6]));
// 输出: [9,9,6,-1,-1]
// 解释:
// 2  → 第一个更大 4,第二个更大 9
// 4  → 第一个更大 9,第二个更大 -1(没有)
// 0  → 第一个更大 9,第二个更大 6
// 9  → 没有更大
// 6  → 没有更大
```

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐