当前位置：首页 > ai >正文

LeetCode 3355.零数组变换 I：差分数组

ai 2025/8/19 4:16:24

【LetMeFly】3355.零数组变换 I：差分数组

力扣题目链接：https://leetcode.cn/problems/zero-array-transformation-i/

给定一个长度为 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：

<ul><li>选择下标子集 <code>[0, 2]</code> 并将这些下标处的值减 1。</li><li>数组将变为 <code>[0, 0, 0]</code>，这是一个零数组。</li>
</ul>
</li>

示例 2：

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

输出： false

解释：

对于 i = 0：

<ul><li>选择下标子集 <code>[1, 2, 3]</code> 并将这些下标处的值减 1。</li><li>数组将变为 <code>[4, 2, 1, 0]</code>。</li>
</ul>
</li>
<li><strong>对于 i = 1：</strong>
<ul><li>选择下标子集 <code>[0, 1, 2]</code> 并将这些下标处的值减 1。</li><li>数组将变为 <code>[3, 1, 0, 0]</code>，这不是一个零数组。</li>
</ul>
</li>

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= l_i <= r_i < nums.length

解题方法：差分数组

创建一个 $o p$ 数组，假设某个query是从 $0$ 到 $3$ ，那么就将 $o p [0]$ 到 $o p [3]$ 都加一(代表下标 $0$ 到 $3$ 都可以被操作一次)，其中 $o p [i]$ 代表 $n u m s [i]$ 一共被操作多少次。

创建一个 $d i ff$ 数组，其中 $d i ff [i]$ 代表数组 $o p [i] - o p [i - 1]$ 的差值。

假设想让 $o p [l]$ 到 $o p [r]$ 都加一，那么其实只需要 $d i ff [l]$ 加一 $d i ff [r + 1]$ 减一， $o p$ 数组直接扔了都行。

执行完所有操作(更新好diff数组)后， $\sum_0^i diff[i]$ 即为 $o p [i]$ 的值。

如果存在任何一个 $i$ 的 $nums[i]\gt op[i]$ ，就说明 $n u m s [i]$ 无法减为 $0$ ，返回false。

时间复杂度 $O (l e n (q u er i es) + l e n (n u m s))$
空间复杂度 $O (l e n (n u m s))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-05-21 23:06:35* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-21 23:14:28*/
class Solution {
public:bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {vector<int> diff(nums.size() + 1);for (vector<int>& q : queries) {diff[q[0]]++;diff[q[1] + 1]--;}int cnt = 0;for (int i = 0; i < nums.size(); i++) {cnt += diff[i];if (nums[i] > cnt) {return false;}}return true;}
};

Python

'''
Author: LetMeFly
Date: 2025-05-21 23:06:35
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-21 23:19:48
'''
from typing import Listclass Solution:def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:diff = [0] * (len(nums) + 1)for l, r in queries:diff[l] += 1diff[r + 1] -= 1cnt = 0for i in range(len(nums)):cnt += diff[i]if nums[i] > cnt:return Falsereturn True

Java

/** @Author: LetMeFly* @Date: 2025-05-21 23:06:35* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-21 23:20:50*/
class Solution {public boolean isZeroArray(int[] nums, int[][] queries) {int[] diff = new int[nums.length + 1];for (int[] q : queries) {diff[q[0]]++;diff[q[1] + 1]--;}int cnt = 0;for (int i = 0; i < nums.length; i++) {cnt += diff[i];if (nums[i] > cnt) {return false;}}return true;}
}

Go

/** @Author: LetMeFly* @Date: 2025-05-21 23:06:35* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-21 23:23:00*/
package mainfunc isZeroArray(nums []int, queries [][]int) bool {diff := make([]int, len(nums) + 1)for _, q := range queries {diff[q[0]]++diff[q[1] + 1]--}cnt := 0for i := 0; i < len(nums); i++ {cnt += diff[i]if nums[i] > cnt {return false}}return true
}