6919. 使数组中的所有元素都等于零 (opens new window)

1.滑动窗口+队列

将问题转化为滑动窗口

基本思想：用双端队列保存滑动窗口内的所有值，规定大小为k的滑动窗口从左往右移动，因此当前滑动窗口左边界元素值m变为0的扣减操作只能在当前滑动窗口进行(因为窗口下次向右移动一个位置后，m再也没有机会执行扣减操作了)。假设窗口内的所有元素减去m后存在小于0的值，那么返回false。

这里如果是传统做法，每次窗口移动令所有元素都减去m，然后再进行判断，那么时间复杂度O(m*k)会超时。因此本题难点就在于如何简化“扣减”和“判断”操作？扣减时能否只算一次？

从问题出发思考+差分数组思想

“窗口移动判断”操作问题本质：对于窗口【i，i+k】，如果移动后窗口内的最大值小于等于num[i+1+k]，说明可以加入窗口。最大值即为num[i+k]扣减掉将第i个位置化零的值，因此问题关键就是计算出当前窗口向右移一格后窗口内的元素应该扣减多少？

• 第一个元素nums[0]所在的窗口移动后，则直接扣减nums[0](前面说过它只能在这个窗口化零)
• i>0，nums[i]刚加入窗口时，假设i-1，i位置的值分别为a1,a2，窗口移动到左边界为 i 时，第i个位置上的值为a2-k-(a1-k)=a2-a1，也就是下一次移动需要扣减的值。这里根据i的范围又分两种情况：
  • 0<i<k，则a1=nums[i-1]，a2=nums[i]
  • i>=k，则a1=nums[i-1] - 上一次移动扣减的值，a2=nums[i]

队列queue【i】保存的元素是当queue【i】移动到queue【0】时，整个窗口向右移动一个位置后nums窗口内每个元素需要扣减的值。而之所以能够这样做，是因为具备以下条件：

• 判断新元素能否加入队列，只会用到一次队尾元素tail进行一次扣减运算得到的结果来作比较。
• 后续滑动窗口内元素在移动的过程中，每次扣减队首元素得到的值并不需要关心和统计。

因此对于下一个元素k，只需要用窗口尾元素减去队列首元素得到差n,如果n大于k，则说明k在后面的扣减过程一定会变为负数；否则将滑动窗口向右移一个位置。

✨而这里每次新入队元素的值，实际上就是差分数组的计算过程。f[i]=nums[i]-nums[i-1]得到相邻两个数的差。

class Solution {
    public boolean checkArray(int[] nums, int k) {
        Deque<Integer> queue = new LinkedList<>();
        int i=1,pre=nums[0];
        queue.offerLast(nums[0]);
        //预处理先填满队列
        while (i<k) {
            if(nums[i]<nums[i-1]) return false;
            queue.offerLast((nums[i] - nums[i - 1]));
            i++;
        }
        
       //队列进出并判断
        for (int m = k; m < nums.length; m++) {
            int sub = queue.pollFirst();
            if(nums[m-1]-sub>nums[m]) return false;
            queue.offerLast(nums[m] + sub - nums[m-1]);
        }
        //判断剩下最后一个窗口是否能够化零
        queue.pollFirst();
        while(queue.size()>0){
            if(queue.pollFirst()!=0) return false;
        }
        return true;
    }
}

2.举例

nums=[3,4,5,6,3,2]，k=4

1. 初始化队列queue=[3,1,1,1]
2. 窗口移动，整个窗口内的所有元素需要扣除队列头结点3，变为[0,1,2,3]，窗口尾节点3小于等于nums下一个元素3，因此3可以加入当前滑动窗口，变为[1,2,3,3]，显然当前一个3移出窗口后，后一个3肯定也变为0，因此队列加入元素0，queue=[1,1,1,0]

nums = [2,2,3,4,1,0], k = 3

1. 初始化队列queue=[2,0,1]
2. 窗口移动，整个窗口内的所有元素需要扣除队列头结点2，窗口元素变为[0,0,1]，窗口尾节点1小于等于nums下一个元素4，因此4可以加入当前滑动窗口，变为[0,1,4]，显然当前一个1移出窗口后，4的最大扣减数为1，因此队列加入元素3，queue=[0,1,3]