链表中的下一个更大节点 图解题解

这道题到底在问什么

输入

head = [2,1,5]

输出

[5,5,0]

输入

head = [2,7,4,3,5]

输出

[7,0,5,5,0]

输入

head = [1]

输出

[0]

最优解：一步一步想明白

1. 3记住:栈里存「还在等更大值」的下标,新值能压倒谁就给谁结算、弹出谁。下面逐帧套它。
2. 4遍历链表:读到第 1 个节点(值 1),把它抄进数组 vals 的下标 0。
3. 5遍历链表:读到第 2 个节点(值 7),把它抄进数组 vals 的下标 1。
4. 6遍历链表:读到第 3 个节点(值 5),把它抄进数组 vals 的下标 2。
5. 7遍历链表:读到第 4 个节点(值 1),把它抄进数组 vals 的下标 3。
6. 8遍历链表:读到第 5 个节点(值 9),把它抄进数组 vals 的下标 4。
7. 9遍历链表:读到第 6 个节点(值 2),把它抄进数组 vals 的下标 5。
8. 10遍历链表:读到第 7 个节点(值 5),把它抄进数组 vals 的下标 6。
9. 11遍历链表:读到第 8 个节点(值 1),把它抄进数组 vals 的下标 7。链表读完,vals 已就绪,下面切到数组上跑单调栈。
10. 12vals 抄好了:柱子高度 = 节点值,柱子下方数字 = 下标。现在从左到右扫一遍,空栈起步,栈里只放「还在等更大值」的下标。
11. 13轮到下标 0(高 1,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
12. 14栈已空,没有可结算的。把当前下标 0 压栈,让它去等自己的下一个更大值。此刻 ans = [0, 0, 0, 0, 0, 0, 0, 0]。
13. 15轮到下标 1(高 7,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
14. 16栈顶是下标 0(高 1,标红),它严格小于当前的 7,说明 7 就是它右边第一个更大值。填 ans[0] = 7,把下标 0 弹出。
15. 17栈已空,没有可结算的。把当前下标 1 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 0, 0, 0, 0, 0, 0, 0]。
16. 18轮到下标 2(高 5,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
17. 19栈顶下标 1(高 7)不比 5 矮,停止弹栈。把当前下标 2 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 0, 0, 0, 0, 0, 0, 0]。
18. 20轮到下标 3(高 1,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
19. 21栈顶下标 2(高 5)不比 1 矮,停止弹栈。把当前下标 3 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 0, 0, 0, 0, 0, 0, 0]。
20. 22轮到下标 4(高 9,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
21. 23栈顶是下标 3(高 1,标红),它严格小于当前的 9,说明 9 就是它右边第一个更大值。填 ans[3] = 9,把下标 3 弹出。
22. 24栈顶是下标 2(高 5,标红),它严格小于当前的 9,说明 9 就是它右边第一个更大值。填 ans[2] = 9,把下标 2 弹出。
23. 25栈顶是下标 1(高 7,标红),它严格小于当前的 9,说明 9 就是它右边第一个更大值。填 ans[1] = 9,把下标 1 弹出。
24. 26栈已空,没有可结算的。把当前下标 4 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 0, 0, 0]。
25. 27轮到下标 5(高 2,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
26. 28栈顶下标 4(高 9)不比 2 矮,停止弹栈。把当前下标 5 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 0, 0, 0]。
27. 29轮到下标 6(高 5,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
28. 30栈顶是下标 5(高 2,标红),它严格小于当前的 5,说明 5 就是它右边第一个更大值。填 ans[5] = 5,把下标 5 弹出。
29. 31栈顶下标 4(高 9)不比 5 矮,停止弹栈。把当前下标 6 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 5, 0, 0]。
30. 32轮到下标 7(高 1,紫色)。先反复比对栈顶:看栈里有没有正在等它的矮个子。
31. 33栈顶下标 6(高 5)不比 1 矮,停止弹栈。把当前下标 7 压栈,让它去等自己的下一个更大值。此刻 ans = [7, 9, 9, 9, 0, 5, 0, 0]。
32. 34扫完整条数组。栈里还剩下标 4, 6, 7(蓝色),它们右边再没有更大的值,答案保持 0。最终 ans = [7, 9, 9, 9, 0, 5, 0, 0],和开头一致。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import Optional, List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        ans = [0] * len(vals)
        st = []
        for i, v in enumerate(vals):
            while st and vals[st[-1]] < v:
                ans[st.pop()] = v
            st.append(i)
        return ans

#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> vals;
        while (head) { vals.push_back(head->val); head = head->next; }
        vector<int> ans(vals.size()), st;
        for (int i = 0; i < (int)vals.size(); ++i) {
            while (!st.empty() && vals[st.back()] < vals[i]) { ans[st.back()] = vals[i]; st.pop_back(); }
            st.push_back(i);
        }
        return ans;
    }
};

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        ArrayList<Integer> vals = new ArrayList<>();
        while (head != null) { vals.add(head.val); head = head.next; }
        int[] ans = new int[vals.size()];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < vals.size(); i++) {
            while (!st.isEmpty() && vals.get(st.peek()) < vals.get(i)) ans[st.pop()] = vals.get(i);
            st.push(i);
        }
        return ans;
    }
}

复杂度

面试官可能追问