当前位置：首页 > article >正文

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

article 2024/9/16 18:52:55

题目链接

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$

解法：单调栈

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

在这里插入图片描述

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

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

时间复杂度： $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;
    }
};