题目描述

给定一个链表的表头节点 head。让我们标号链表中的结点为：node_1，node_2，node_3，等等。

每个结点有下一个比它大的值：对于 node_i 来说，next_larger(node_i) 是结点 node_j.val 使得 node_j.val > node_i.val，j 是尽可能小的选择。如果这样的 j 不存在，下一个较大值就是 0。

返回整数数组 answer，answer[i] = next_larger(node_{i+1})。

注意到在下方的样例输入中，数组 [2,1,5] 表示一个序列化的链表，头结点的值为 2，第二个结点的值为 1，第三个结点的值为 5。

样例

输入：[2,1,5]
输出：[5,5,0]

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

输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]

注意

• 对于链表中的所有结点，1 <= node.val <= 10^9。
• 给定链表的长度在 [0, 10000] 中。

算法

(单调栈) $O(n)$

1. 此题就是要求每个结点之后第一个比当前点大的值。
2. 这是单调栈的例题，维护一个单调递减的栈，如果当前元素比栈顶元素大，则持续出栈直到不满足这个条件。这些出栈的元素的答案就是当前元素，然后当前元素进栈。
3. 最后还在栈中的元素的答案就是 0。

时间复杂度

• 每个元素进栈一次，出栈一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的数组和栈空间，故空间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> A;
        ListNode *cur = head;
        while (cur != NULL) {
            A.push_back(cur -> val);
            cur = cur -> next;
        }

        int n = A.size();
        stack<int> s;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            while (!s.empty() && A[i] > A[s.top()]) {
                ans[s.top()] = A[i];
                s.pop();
            }
            s.push(i);
        }
        while (!s.empty()) {
            ans[s.top()] = 0;
            s.pop();
        }
        return ans;
    }
};