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

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]
示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

提示：

链表中节点数为 n
1 <= n <= 104^44
1 <= Node.val <= 109^99

将链表转换为数组，然后使用单调栈即可：

/** * 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) {} * }; */classSolution{public:vector<int>nextLargerNodes(ListNode*head){vector<int>ans;ListNode*node=head;while(node){ans.push_back(node->val);node=node->next;}stack<int>stk;for(inti=ans.size()-1;i>=0;--i){while(!stk.empty()&&ans[i]>=stk.top()){stk.pop();}intcurValue=ans[i];if(!stk.empty()){ans[i]=stk.top();}else{ans[i]=0;}stk.push(curValue);}returnans;}};

如果链表长度为n，则此算法时间复杂度为O(n)，空间复杂度为O(n)。