2487. 从链表中移除节点
给你一个链表的头节点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 ，所以没有需要移除的节点。
题目分析
解题思路：维持一个单调递增栈，当栈为空时，记录当前节点为头节点；否则当前节点为栈顶节点的后继节点
单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈
单调栈详解及相关 Leetcode 题解见 Leetcode 单调栈详解
public ListNode removeNodes(ListNode head) {
Deque<ListNode> stack = new ArrayDeque<>();
ListNode tmpHead = head;
while (head != null){
// 单调递增栈
while(!stack.isEmpty() && head.val > stack.peek().val){
stack.pop();
}
// 栈为空，说明当前节点是目前遍历到的最大值，设置为头节点；否则当前节点为栈顶节点的后继节点
if (stack.isEmpty()) {
tmpHead = head;
} else {
stack.peek().next = head;
}
stack.push(head);
head = head.next;
}
return tmpHead;
}
