力扣周赛 T3 6080. 使数组按非递减顺序排列 没做出来复盘_给你一个下标从 0 开始的整数数组 nums 。在一步操作中,移除所有满足 nums[i - 1]

6080. 使数组按非递减顺序排列

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

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

示例 1：

输入：nums = [5,3,4,4,7,3,6,11,8,5,11]
输出：3
解释：执行下述几个步骤：
- 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]
- 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]
- 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11]
[5,7,11,11] 是一个非递减数组，因此，返回 3 。

示例 2：

输入：nums = [4,5,7,7,13]
输出：0
解释：nums 已经是一个非递减数组，因此，返回 0 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/steps-to-make-array-non-decreasing/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

赛后听说链表模拟能写，随便改了改就过了，我真是太笨了

1. 建立链表尾节点

2. 倒查数组，把每个节点接在后一个节点的前面（例如 5 4 3,4 和 3 本轮都可以删除，倒着放可以满足一轮同时删掉 4 和 3）

3. 如果是合适的节点，加入队列

4. 类似层次遍历，一层层查，还比下一个大，再放回去

5. 每经过一层，证明经过一轮操作，操作数加 1

细节

一定要倒着查，正着删会漏掉，如 5 4 3 ，4 删掉了，后面在队列中再拿到4，不好处理

class Solution {
    public int totalSteps(int[] nums) {
        Node last = new Node(0);
        Node curr = last;
        Queue<Node> queue = new LinkedList<>();
        int n = nums.length;
        for(int i = n-1; i >= 0; i--){
            int num = nums[i];
            Node v = new Node(num);
            v.next = curr;
            curr = v;
            if(curr.next!=last && curr.val > curr.next.val){
                queue.offer(curr);
            }
 
        }
        int ans = 0;
        while (!queue.isEmpty()){
            ++ans;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                Node node =queue.poll();
                node.next = node.next.next;
                if(node.next!=last&&node.val > node.next.val){
                    queue.offer(node);
                }
            }
        }
        return ans;
    }
 
    class Node{
        Node next;
        int val;
        public Node(int val){
            this.val = val;
        }
    }
}

感想：对于一个方法死磕写不出来的（尤其像贪心、单调栈、动态规划），可尝试换换思路

 评论