1019. 链表中的下一个更大节点

题目地址(1019. 链表中的下一个更大节点)

https://leetcode-cn.com/problems/next-greater-node-in-linked-list/

题目描述

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。

每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且  node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。

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

注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。



示例 1：

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

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

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


提示：

对于链表中的每个节点，1 <= node.val <= 10^9
给定列表的长度在 [0, 10000] 范围内

前置知识

• 链表

• 栈

公司

• 腾讯

• 字节

思路

看完题目就应该想到单调栈才行，LeetCode 上关于单调栈的题目还不少，难度都不小。但是一旦你掌握了这个算法，那么这些题目对你来说都不是问题了。

如果你不用单调栈，那么可以暴力$O(N^2)$的时间复杂度解决，只需要双层循环即可。但是这种做法应该是过不了关的。使用单调栈可以将时间复杂度降低到线性，当然需要额外的$O(N)$的空间复杂度。

顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。为了描述方便，以下举例及代码以维护一个整数的单调递减栈为例。将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例如，栈中自顶向下的元素为 1，2，4，5 ，插入元素 3 时为了保证单调性需要依次弹出元素 :

• 最开始栈是这样的： [5,4,2,1]

• 为了维护递减特性，1,2 需要被移除。此时栈是这样的： [5,4]

• 我们将 3 push 到栈顶即可

• 此时栈是这样的： [5,4,3]

用代码描述如下：

Python Code:

def monoStack(list):
    st = []
    for v in list:
        while len(st) > 0 and v > st[-1]:
            st.pop()
        st.append(v)
    return st
monoStack([5, 4, 2, 1, 3]) # output: [5, 4, 3]

关键点

• 单调栈（单调递减栈）

• 单调栈的代码模板

代码

Python Code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
     def nextLargerNodes(self, head):
        res, st = [], []
        while head:
            while len(st) > 0 and head.val > st[-1][1]:
                res[st.pop()[0]] = head.val
            st.append((len(res), head.val))
            res.append(0)
            head = head.next
        return res

复杂度分析

其中 N 为链表的长度。

• 时间复杂度：$O(N)$

• 空间复杂度：$O(N)$

扩展

甚至可以做到 O(1)的空间复杂度，请参考[C# O(n) time O(1) space](https://leetcode.com/problems/next-greater-node-in-linked-list/discuss/267090/C-O(n)-time-O(1)-space)

相关题目

• 毎日一题 - 739.Daily Temperatures