给定一个长度为 n 的链表 head对于列表中的每个节点查找下一个 更大节点 的值。也就是说对于每个节点找到它旁边的第一个节点的值这个节点的值 严格大于 它的值。返回一个整数数组 answer 其中 answeri 是第 i 个节点 从1开始 的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点设置 answeri = 0 。请编写程序实现

算法思路：

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

具体过程如下：

• 初始化结果数组 answer 为0，初始化栈为空。

• 从头到尾遍历链表，对于每个节点进行如下操作：

• 当栈不为空且当前节点的值大于栈顶节点的值时，栈顶节点的下一个更大节点为当前节点的值。我们将栈顶节点弹出，并将其下一个更大节点设置为当前节点的值。

• 将当前节点入栈。

• 最后返回结果数组 answer。

算法实现：

C++ 代码

class Solution { public: vector nextLargerNodes(ListNode* head) { vector 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; } };