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

题目链接

Leetcode.1019 链表中的下一个更大节点 Rating ： 1571

题目描述

给定一个长度为 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<=10^4$
• $1<=Node.val<=10^9$

解法：单调栈

对于每一个结点 $node$ ，我们考虑 它 是哪些结点的 下一个更大的结点。

对于 结点$y$来说，它是 结点$x1,x2,x3,x4$的 下一个更大节点。当我们把结点$x1,x2,x3,x4$的下一个更大结点记录下来之后，这些结点就没用了，我们就可以把它们弹出去。

所以我们实际上维护的是一个 底大顶小的单调栈。当我们弹出栈顶元素的时候，就对每一个位置的下一个最大节点做更新。为了方便更新，我们需要记录下标。

时间复杂度： $O(n)$

C++代码：

using PII = pair<int,int>;

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> ans;
        //节点值 和 对应得下标
        stack<PII> stk;

        while(head != nullptr){
            while(!stk.empty() && stk.top().first < head->val){
                ans[stk.top().second] = head->val;
                stk.pop();
            }

            stk.emplace(head->val,ans.size());
            ans.push_back(0);
            head = head->next;
        }

        return ans;
    }
};