Medium

题目描述

给定一个长度为 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

解题思路

这道题本质上是求每个元素的下一个更大元素，是经典的单调栈问题。

核心思路：

  1. 遍历链表时，维护一个单调递减栈，栈中存储节点的索引
  2. 当遇到一个新节点时，如果它的值大于栈顶对应节点的值，说明找到了栈顶元素的下一个更大元素
  3. 持续弹出栈顶，直到栈为空或栈顶对应的值不小于当前节点值
  4. 将当前节点索引入栈

算法步骤：

  1. 首先遍历链表，将所有值存入数组（因为需要随机访问）
  2. 初始化结果数组，默认值为0
  3. 使用栈存储索引，遍历数组：
    • 当栈不为空且当前元素大于栈顶索引对应的元素时，更新结果数组
    • 将当前索引入栈

这种方法时间复杂度为O(n)，因为每个元素最多入栈和出栈一次。空间复杂度为O(n)，用于存储栈和结果数组。

推荐解法：单调栈 - 时间最优，代码简洁

代码实现

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> values;
        ListNode* curr = head;
        
        // 将链表值存入数组
        while (curr) {
            values.push_back(curr->val);
            curr = curr->next;
        }
        
        vector<int> result(values.size(), 0);
        stack<int> st; // 存储索引
        
        for (int i = 0; i < values.size(); i++) {
            // 当前元素大于栈顶索引对应的元素时，更新结果
            while (!st.empty() && values[i] > values[st.top()]) {
                result[st.top()] = values[i];
                st.pop();
            }
            st.push(i);
        }
        
        return result;
    }
};

class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        values = []
        curr = head
        
        # 将链表值存入列表
        while curr:
            values.append(curr.val)
            curr = curr.next
        
        result = [0] * len(values)
        stack = []  # 存储索引
        
        for i in range(len(values)):
            # 当前元素大于栈顶索引对应的元素时，更新结果
            while stack and values[i] > values[stack[-1]]:
                result[stack.pop()] = values[i]
            stack.append(i)
        
        return result

public class Solution {
    public int[] NextLargerNodes(ListNode head) {
        var values = new List<int>();
        var curr = head;
        
        // 将链表值存入列表
        while (curr != null) {
            values.Add(curr.val);
            curr = curr.next;
        }
        
        var result = new int[values.Count];
        var stack = new Stack<int>(); // 存储索引
        
        for (int i = 0; i < values.Count; i++) {
            // 当前元素大于栈顶索引对应的元素时，更新结果
            while (stack.Count > 0 && values[i] > values[stack.Peek()]) {
                result[stack.Pop()] = values[i];
            }
            stack.Push(i);
        }
        
        return result;
    }
}

var nextLargerNodes = function(head) {
    const values = [];
    let curr = head;
    
    // 将链表值存入数组
    while (curr) {
        values.push(curr.val);
        curr = curr.next;
    }
    
    const result = new Array(values.length).fill(0);
    const stack = []; // 存储索引
    
    for (let i = 0; i < values.length; i++) {
        // 当前元素大于栈顶索引对应的元素时，更新结果
        while (stack.length > 0 && values[i] > values[stack[stack.length - 1]]) {
            result[stack.pop()] = values[i];
        }
        stack.push(i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多入栈和出栈一次，链表遍历O(n)
空间复杂度O(n)栈的最大空间为O(n)，额外数组存储链表值O(n)