DeepSeek LeetCode 2454.下一个更大元素 IV JavaScript实现
这是 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 → 没有更大
```
更多推荐


所有评论(0)