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

思路：单调栈模板题

Accode：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> ans;
        stack<pair<int,ListNode*>>sta;
        // int cnt = 1;
        while(head!=nullptr){
            ans.push_back(0);
            while(sta.size() && sta.top().second->val < head->val ){
                ans[sta.top().first] = head->val;
                sta.pop();
            }
            sta.push({ans.size()-1,head});
            head = head->next;
        }
        return ans;
    }
};

时间复杂度：$o(n)$n为链表的长度