3355. 零数组变换 I

来源第 424 场周赛 Q2难度中等分数1591

题目描述

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

对于每个查询 queries[i]：

在 nums 的下标范围 [l_i, r_i] 内选择一个下标子集。
将选中的每个下标对应的元素值减 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⁵
0 <= nums[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= l_i <= r_i < nums.length

解法

方法一：差分数组

思考

每个询问把 \([l,r]\) 各减一（实际是提供一次覆盖），问全部询问用完后能否把 \(\textit{nums}\) 盖到 \(0\)。\(n,m \le 10^5\)，不能逐询问改数组。

覆盖次数是区间加，差分数组在 \(l\) 加一、\(r+1\) 减一，前缀和即每位被覆盖次数。

若某位 \(\textit{nums}[i]\) 大于覆盖次数，则无法归零。

我们可以使用差分数组来解决这个问题。

定义一个长度为 \(n + 1\) 的数组 \(d\)，初始值全部为 \(0\)。对于每个查询 \([l, r]\)，我们将 \(d[l]\) 加 \(1\)，将 \(d[r + 1]\) 减 \(1\)。

然后我们遍历数组 \(d\) 在 \([0, n - 1]\) 范围内的每个元素，累加前缀和 \(s\)，如果 \(\textit{nums}[i] > s\)，说明 \(\textit{nums}\) 不能转换为零数组，返回 \(\textit{false}\)。

遍历结束后，返回 \(\textit{true}\)。

时间复杂度 \(O(n + m)\)，空间复杂度 \(O(n)\)。其中 \(n\) 和 \(m\) 分别为数组 \(\textit{nums}\) 和 \(\textit{queries}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        d = [0] * (len(nums) + 1)
        for l, r in queries:
            d[l] += 1
            d[r + 1] -= 1
        s = 0
        for x, y in zip(nums, d):
            s += y
            if x > s:
                return False
        return True

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] d = new int[n + 1];
        for (var q : queries) {
            int l = q[0], r = q[1];
            ++d[l];
            --d[r + 1];
        }
        for (int i = 0, s = 0; i < n; ++i) {
            s += d[i];
            if (nums[i] > s) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int d[n + 1];
        memset(d, 0, sizeof(d));
        for (const auto& q : queries) {
            int l = q[0], r = q[1];
            ++d[l];
            --d[r + 1];
        }
        for (int i = 0, s = 0; i < n; ++i) {
            s += d[i];
            if (nums[i] > s) {
                return false;
            }
        }
        return true;
    }
};

func isZeroArray(nums []int, queries [][]int) bool {
    d := make([]int, len(nums)+1)
    for _, q := range queries {
        l, r := q[0], q[1]
        d[l]++
        d[r+1]--
    }
    s := 0
    for i, x := range nums {
        s += d[i]
        if x > s {
            return false
        }
    }
    return true
}

function isZeroArray(nums: number[], queries: number[][]): boolean {
    const n = nums.length;
    const d: number[] = Array(n + 1).fill(0);
    for (const [l, r] of queries) {
        ++d[l];
        --d[r + 1];
    }
    for (let i = 0, s = 0; i < n; ++i) {
        s += d[i];
        if (nums[i] > s) {
            return false;
        }
    }
    return true;
}

3355. 零数组变换 I

题目描述

解法

方法一：差分数组

评论