难度: 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]
提示：
n1 <= n <= 1041 <= Node.val <= 109运行时间: 99 ms
内存: 19.2 MB
# Definition for singly-linked 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]:
'''下一个最大问题: 考虑使用单调栈'''
val_list = []
cur = head
while cur:
value = cur.val
val_list.append(value)
cur = cur.next
st = []
res = [0] * len(val_list)
for i, val in enumerate(val_list):
while st and val > val_list[st[-1]]:
j = st.pop()
res[j] = val
st.append(i)
return res
这个解决方案首先将链表的值转换为一个列表，然后利用单调栈解决'下一个更大的元素'问题。通过遍历链表将所有值存储在列表中，随后使用单调栈技术来快速查找每个元素右侧第一个更大的值。遍历值列表时，对于每个元素，检查栈顶元素是否代表一个较小的值。如果是，栈顶元素出栈并更新结果数组，表明找到了较小元素右侧的更大值。如果当前元素不比栈顶元素大，或栈为空，则当前元素索引入栈。这样确保栈内元素始终保持单调递减。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for singly-linked 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]:
# 使用单调栈解决下一个更大的节点问题
val_list = [] # 将链表的值存储到列表中
cur = head # 初始化当前节点为头节点
while cur:
value = cur.val # 获取当前节点的值
val_list.append(value) # 添加到列表中
cur = cur.next # 移动到下一个节点
st = [] # 初始化单调栈
res = [0] * len(val_list) # 初始化结果数组，所有值默认为0
for i, val in enumerate(val_list): # 遍历每个节点值
while st and val > val_list[st[-1]]: # 如果栈不空，且当前值大于栈顶值
j = st.pop() # 弹出栈顶元素
res[j] = val # 更新结果数组
st.append(i) # 当前元素索引入栈
return res # 返回结果数组
单调栈保持元素索引的单调递减，主要是为了快速找到每个元素右侧第一个更大的元素。这种设计允许在遍历元素时，一旦当前元素大于栈顶元素，即可立即确定栈顶元素的下一个更大节点，并将其出栈。这样的处理方式极大地提高了算法的效率，因为每个元素最多被压入和弹出栈一次，从而使得整个算法时间复杂度保持在O(n)。
在单调栈的使用中，虽然栈中元素可能很少，但列表很大的情况不会对算法性能产生负面影响。这是因为每个元素无论如何都需要遍历一次，而栈中的操作（压栈和弹栈）的总次数与元素总数成正比。所以，整个算法的时间复杂度仍然是O(n)，这里n是列表中元素的数量。无论栈中有多少元素，每个元素进栈和出栈的总次数不超过n次。
函数返回的数组`res`初始化为全0是合理的，因为这代表了每个节点没有找到右侧更大的值的默认情况。在单调栈的处理过程中，只有当找到一个更大的值时才会更新数组的相应位置。如果链表中的所有元素都没有更大的值，那么结果数组保持为0是符合期望的输出，因此这种初始化方式是适当的，免去了额外的条件判断和赋值操作。
链表转数组的方法在处理非常长的链表时，可能会面临效率和实用性的问题。首先，这需要遍历整个链表来构建数组，这个过程本身就是O(n)的时间复杂度。其次，如果链表非常长，相应的数组也会很大，这可能导致较高的内存消耗。再者，如果链表结构已经足够支持所需的操作，那么转换为数组可能是不必要的。不过，对于下一个更大节点的查找，使用数组可以方便地通过索引访问元素，这在链表中是不容易做到的。