【Leetcode 2487】从链表中移除节点 —— 单调栈

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;
}