题目描述

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

对于每个查询 queries[i]：

• 在 nums 的下标范围 [l_i, r_i] 内选择一个下标子集。
• 将选中的每个下标对应的元素值减 1。

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

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

数组的 子集 是对数组元素的选择（可能为空）。

样例

输入： nums = [1,0,1], queries = [[0,2]]

输出： true

解释：

对于 i = 0：
    选择下标子集 [0, 2] 并将这些下标处的值减 1。
    数组将变为 [0, 0, 0]，这是一个零数组。

输入： 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 <= l_i <= r_i < nums.length

算法

(差分数组) $O(n + q)$

1. 对于每个查询，都在其左端点的位置增加 1，在右端点的 下一个 位置减少 1。
2. 然后求上述操作后的每个位置的前缀和，其值就是这个位置最多可以被减少的数值。

时间复杂度

• 遍历每个查询一次，遍历数组一次，故时间复杂度为 $O(n + q)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储差分数组。

C++ 代码

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        const int n = nums.size();
        vector<int> p(n + 1, 0);

        for (const auto &q : queries) {
            ++p[q[0]];
            --p[q[1] + 1];
        }

        int s = 0;
        for (int i = 0; i < n; i++) {
            s += p[i];
            if (s < nums[i])
                return false;
        }

        return true;
    }
};