单调栈
解题思路
维护一个单调递减栈，每个元素都与栈顶元素比较，比栈顶元素大则出栈并更新 结果数组；
由于该题是 链表 ，则需要把 索引 和 值 都存起来，放入栈中，这样比较的时候，可以更新对应索引的结果；
复杂度
-
时间复杂度:
O(n)，其中 n 是链表的长度； -
空间复杂度:
O(n)，其中 n 是链表的长度，栈的大小至多为 n；
代码实现
var nextLargerNodes = function (head) {
// 1. 声明一个单调递减的栈
const stack = [];
const res = [];
let inx = 0;
// 2. 在栈中寻找下一个更大的值
while (head) {
while (stack.length && stack[stack.length - 1][0] < head.val) {
res[stack.pop()[1]] = head.val;
}
res[inx] = 0; // 默认值
stack.push([head.val, inx++]); // 需要将值和索引都存储起来
head = head.next;
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 449. 序列化和反序列化二叉搜索树
上一篇
评论
