1019.链表中的下一个更大节点

链接：1019.链表中的下一个更大节点
难度：Medium
标签：栈、数组、链表、单调栈
简介：返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

题解 1 - cpp

• 编辑时间：2023-04-10
• 执行用时：72ms
• 内存消耗：43.8MB
• 编程语言：cpp
• 解法介绍：单调栈。

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        int idx = 0;
        ListNode *tmp = head;
        vector<int> vlist, res;
        stack<int> s;
        while (tmp) {
            vlist.push_back(tmp->val);
            res.push_back(0);
            while (s.size() && vlist[s.top()] < tmp->val) {
                int top = s.top();
                s.pop();
                res[top] = tmp->val;
            }
            s.push(idx);
            idx++;
            tmp = tmp->next;
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-04-10
• 执行用时：220ms
• 内存消耗：19.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        idx = 0
        tmp = head
        vlist, res, s = [], [], []
        while tmp:
            vlist.append(tmp.val)
            res.append(0)
            while len(s) and vlist[s[-1]] < tmp.val:
                res[s.pop()] = tmp.val
            s.append(idx)
            idx += 1
            tmp = tmp.next
        return res

题解 3 - rust

• 编辑时间：2023-04-10
• 执行用时：24ms
• 内存消耗：2.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut tmp = &head;
        let mut idx = 0;
        let mut vlist = vec![];
        let mut res = vec![];
        let mut s = vec![];
        while let Some(ref node) = tmp {
            vlist.push(node.val);
            res.push(0);
            while !s.is_empty() && vlist[*s.last().unwrap()] < node.val {
                res[s.pop().unwrap()] = node.val;
            }
            s.push(idx);
            idx += 1;
            tmp = &node.next;
        }
        res
    }
}