链表中每个节点的下一个更大节点 - 算法详解与代码实现 - 常规

链表中每个节点的下一个更大节点 - 算法详解与代码实现

问题描述：

给定一个长度为 n 的链表 head，对于列表中的每个节点，查找下一个更大节点的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。

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

算法思路：

这个问题可以使用单调栈解决。我们可以从头到尾扫描链表，并用一个栈来存储还没有找到下一个更大节点的节点。对于每个新的节点，我们首先将所有在栈中的节点的值小于当前节点值的节点的下一个更大节点设置为当前节点的值。然后我们将当前节点推入栈中，等待将来的处理。

具体过程如下：

初始化结果数组 answer 为0，初始化栈为空。
从头到尾遍历链表，对于每个节点进行如下操作：
- 当栈不为空且当前节点的值大于栈顶节点的值时，栈顶节点的下一个更大节点为当前节点的值。我们将栈顶节点弹出，并将其下一个更大节点设置为当前节点的值。
- 将当前节点入栈。
最后返回结果数组 answer。

算法实现：

C++ 代码

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> answer;
        stack<pair<int, int>> st;
        int index = 0;
        while (head != nullptr) {
            answer.push_back(0);
            while (!st.empty() && st.top().second < head->val) {
                answer[st.top().first] = head->val;
                st.pop();
            }
            st.push(make_pair(index++, head->val));
            head = head->next;
        }
        return answer;
    }
};

代码解释：

初始化一个空栈 st 用于存储节点及其索引。
初始化一个结果数组 answer，大小与链表相同，初始值为 0。
遍历链表，对于每个节点：
- 如果栈不为空且当前节点的值大于栈顶节点的值，则将栈顶节点的下一个更大节点设置为当前节点的值，并弹出栈顶节点。
- 将当前节点及其索引入栈。
遍历结束后，返回结果数组 answer。

复杂度分析：

时间复杂度：O(n)，其中 n 是链表的长度。
空间复杂度：O(n)，栈的最大深度为 n。

总结：

本文介绍了如何使用单调栈算法找到链表中每个节点的下一个更大节点，并提供了详细的算法思路、步骤以及 C++ 代码实现。单调栈是一种常用的数据结构，可以用来解决许多类似的问题。