题目
给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。
示例 1：
输入：head = [5,2,13,3,8]
输出：[13,8]
解释：需要移除的节点是 5 ，2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。
示例 2：
输入：head = [1,1,1,1]
输出：[1,1,1,1]
解释：每个节点的值都是 1 ，所以没有需要移除的节点。
提示：
给定列表中的节点数目在范围 [1, 105] 内
1 <= Node.val <= 105
Problem: 2487. 从链表中移除节点
思路
使用单调栈，保留从左到右单调递减的数组，赋值给节点
在单调栈构造时，我们维护一个非递增的数组
如果发现下一个节点大于栈顶元素，则一直弹出栈顶元素，直到栈为空，或者栈顶元素大于下一个节点
复杂度
O ( n ) O(n)O(n)
添 O ( n ) O(n)O(n)
Code
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]: stack = [] index = head while index!=None: while stack!=[] and stack[-1]<index.val: stack.pop() stack.append(index.val) index = index.next index = head for i in range(len(stack)): index.val = stack[i] if i!=len(stack)-1: index = index.next if index!=None : index.next = None return head
