2289. Steps to Make Array Non-decreasing #

题目 #

给定一个下标从 0 开始的整数数组 nums。在一步操作中，移除所有满足 nums[i-1] > nums[i] 的 nums[i]，其中 0 < i < nums.length。

重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。

思路 #

代码 #

class Solution {
    /** 观察: 如果一个结点的左侧结点未发生变化，则该结点在本轮不会被删除
      * 推论: 仅有被删除的结点会触发下一轮删除。当某结点被删除时，考虑是否将被删除结点的下一个结点纳入下一轮删除的列表里
      */
    
    private class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
        
        ListNode(int val, ListNode prev, ListNode next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
    
    public int totalSteps(int[] nums) {
        ListNode sentinel = new ListNode(-1, null, null);
        sentinel.prev = sentinel.next = sentinel;
        
        /** 逆序遍历数组，将其转化为双向链表
          * 若数组的某个元素满足删除条件，则将相应的结点记录在队列中
          */
        Queue<ListNode> deletePoints = new LinkedList<>();
        for (int i=nums.length - 1; i >= 0; i--) {
            sentinel.next = new ListNode(nums[i], sentinel, sentinel.next);
            sentinel.next.next.prev = sentinel.next;
            if (i >= 1 && nums[i] < nums[i-1]) deletePoints.offer(sentinel.next);
        }
        
        /** 对需要执行的操作数进行计数 */
        int step = 0;
        while (deletePoints.size() != 0) {
            step += 1;
            
            Queue<ListNode> newDeletePoints = new LinkedList<>();
            for (ListNode node: deletePoints) {
                if (node.next != sentinel && node.next.val < node.prev.val) {
                    /** 避免某待删除结点被重复添加 */
                    if (newDeletePoints.peek() != node.next) newDeletePoints.offer(node.next);
                }
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            
            deletePoints = newDeletePoints;
        }
        
        return step;
    }
}