题目描述

题目描述

题目意思，即二维数组queries的每个元素表示每次要处理的nums数组的下标子集，如果处理完之后，可将nums变为零数组，返回true。

算法思路

每次要处理某个下标范围（或者子集）的内nums数组，看其能否全变为0，那么我们每次都处理[l,r]范围内的数据，将其-1，这种情况一定是能让nums数组中元素变为最小值的。因此，如果该情况都不能够让所有nums的元素小于等于0，那么就不可以变为零数组。

代码实现

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        boolean ans=true;
        for(int i=0;i<queries.length;i++){
            int l=queries[i][0],r=queries[i][1];
            for(int j=l;j<=r;j++){
                if(nums[j]>0) nums[j]--;
            }
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                ans=false;
                break;
            }
        }
        return ans;
    }
}

超时的情况

优化算法

使用差分数组来记录区间操作，最后统计每个位置被减了多少次。
1.差分数组diff：
diff[i]表示nums[i]比nums[i-1]多减了几次。
对区间[l,r]上的减法，可以转化为：diff[l]--（表示从l开始减1），diff[r+1]++（表示在r+1处取消减1）
2.计算最终减的次数：
遍历diff数组，累加差分值，得到每个位置nums[i]都被减了多少次（即为detail[i]），如果nums[i]-detail[i]>0，说明无法减到0，返回false。

代码实现

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1]; // 差分数组

        // 处理所有查询
        for (int[] q : queries) {
            int l = q[0], r = q[1];
            diff[l]--;
            if (r + 1 < n) diff[r + 1]++;
        }

        // 计算每个位置的 delta（总共减了多少次）
        int delta = 0;
        for (int i = 0; i < n; i++) {
            delta += diff[i];
            if (nums[i] + delta > 0) { // nums[i] - (-delta) > 0
                return false;
            }
        }
        return true;
    }
}

此时的时间复杂度为O（m+n），m是查询数，n是数组长度。
空间复杂度为O（n），n为差分数组所占空间。