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

题目链接：1019. 链表中的下一个更大节点

方法：单调栈

解题思路

该类问题详解：单调栈解决 Next Greater Number 一类问题

代码

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> value;
        while (head != nullptr) {
            value.push_back(head->val);
            head = head->next;
        }
        int n = value.size();
        vector<int> ans(n);
        stack<int> stk;
        stk.push(value.back());
        for (int i = n - 1; i >= 0; i -- ) {
            while (!stk.empty() && value[i] >= stk.top()) stk.pop();
            ans[i] = stk.empty() ? 0 : stk.top();
            stk.push(value[i]);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(n)；
空间复杂度：O(n)。