Medium

题目描述

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个 queries[i]：

  • 在 nums 中选择范围 [li, ri] 内的一个子集
  • 将选中位置的值减1

零数组是所有元素都等于0的数组。

如果在按顺序处理所有查询后，能够将 nums 变换为零数组，返回 true，否则返回 false。

示例 1：

输入：nums = [1,0,1], queries = [[0,2]]
输出：true
解释：
对于 i = 0：
- 选择索引子集 [0, 2]，将这些位置的值减1
- 数组变为 [0, 0, 0]，这是一个零数组

示例 2：

输入：nums = [4,3,2,1], queries = [[1,3],[0,2]]
输出：false
解释：
对于 i = 0：
- 选择索引子集 [1, 2, 3]，将这些位置的值减1
- 数组变为 [4, 2, 1, 0]
对于 i = 1：
- 选择索引子集 [0, 1, 2]，将这些位置的值减1  
- 数组变为 [3, 1, 0, 0]，不是零数组

约束条件：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= li <= ri < nums.length

解题思路

解题思路

这道题的核心思想是统计每个位置最多能被减少多少次，然后判断是否足以将该位置变为0。

方法一：差分数组 + 前缀和（推荐）

每个查询 [li, ri] 表示我们可以在范围 [li, ri] 内选择任意位置进行减1操作。为了让数组变为零数组，我们希望尽可能多地利用这些操作。

最优策略是：对于每个位置，如果它在某个查询范围内，我们就利用这个查询来减少该位置的值。

使用差分数组来高效计算每个位置最多能被减少的次数：

  1. 对于每个查询 [li, ri]，在差分数组的 li 位置+1，在 ri+1 位置-1
  2. 对差分数组求前缀和，得到每个位置能被减少的最大次数
  3. 检查每个位置的减少次数是否大于等于原始值

方法二：暴力模拟

直接模拟每个查询的过程，但时间复杂度较高，不推荐。

差分数组的方法时间复杂度为 O(n + m)，其中 n 是数组长度，m 是查询数量，是最优解法。

代码实现

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> diff(n + 1, 0);
        
        // 构建差分数组
        for (auto& query : queries) {
            int left = query[0], right = query[1];
            diff[left]++;
            diff[right + 1]--;
        }
        
        // 计算前缀和，得到每个位置能被减少的次数
        int reductions = 0;
        for (int i = 0; i < n; i++) {
            reductions += diff[i];
            if (reductions < nums[i]) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        n = len(nums)
        diff = [0] * (n + 1)
        
        # 构建差分数组
        for left, right in queries:
            diff[left] += 1
            diff[right + 1] -= 1
        
        # 计算前缀和，得到每个位置能被减少的次数
        reductions = 0
        for i in range(n):
            reductions += diff[i]
            if reductions < nums[i]:
                return False
        
        return True

public class Solution {
    public bool IsZeroArray(int[] nums, int[][] queries) {
        int n = nums.Length;
        int[] diff = new int[n + 1];
        
        // 构建差分数组
        foreach (var query in queries) {
            int left = query[0], right = query[1];
            diff[left]++;
            diff[right + 1]--;
        }
        
        // 计算前缀和，得到每个位置能被减少的次数
        int reductions = 0;
        for (int i = 0; i < n; i++) {
            reductions += diff[i];
            if (reductions < nums[i]) {
                return false;
            }
        }
        
        return true;
    }
}

var isZeroArray = function(nums, queries) {
    const n = nums.length;
    const diff = new Array(n + 1).fill(0);
    
    // 构建差分数组
    for (const [left, right] of queries) {
        diff[left]++;
        diff[right + 1]--;
    }
    
    // 计算前缀和，得到每个位置能被减少的次数
    let reductions = 0;
    for (let i = 0; i < n; i++) {
        reductions += diff[i];
        if (reductions < nums[i]) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n + m)
空间复杂度O(n)

其中 n 是数组 nums 的长度，m 是查询数量。

相关题目