单调栈
解题思路
维护一个单调递减栈，每个元素都与栈顶元素比较，比栈顶元素大则出栈并更新 结果数组；
由于该题是 循环数组 ，则循环的次数为双倍即可求出最后面元素的 下一个更大的元素；
可以使用 取模运算 % 把下标 i 映射到数组 nums 长度的 0 - N 内；
复杂度
-
时间复杂度:
O(n)，其中 n 是序列的长度，需要遍历该数组中每个元素最多 2 次，每个元素出栈与入栈的总次数也不超过 4 次； -
空间复杂度:
O(n)，其中 n 是序列的长度，空间复杂度主要取决于栈的大小，栈的大小至多为 2n-1；
代码实现
var nextGreaterElements = function (nums) {
// 1. 结果数组默认全部填充 -1，栈中剩余的元素找不到「下一个更大的元素」，为 -1
const stack = [], len = nums.length, res = new Array(len).fill(-1);
// 2. 找到下一个更大的元素
for (let i = 0; i < len * 2; i++) {
let num = nums[i % len];
while (stack.length && num > nums[stack[stack.length - 1]]) {
res[stack.pop()] = num;
}
stack.push(i % len);
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 496. 下一个更大元素Ⅰ
上一篇
评论
