3355、[中等] 零数组变换 Ⅰ
1、题目描述
给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。
对于每个查询 queries[i]：
- 在
nums的下标范围[li, ri]内选择一个下标子集。 - 将选中的每个下标对应的元素值减 1。
零数组 是指所有元素都等于 0 的数组。
如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。
数组的 子集 是对数组元素的选择（可能为空）。
2、解题思路
首先告诉大家，暴力过不了，超时了，打竞赛的时候第一反应还是首选暴力，最后浪费五分钟，下面是暴力代码
class Solution {
public:bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();// 处理每个查询for (const auto& query : queries) {int left = query[0], right = query[1];while (left <= right) {nums[left++]--;}}// 验证for (const auto& num : nums) {if (num > 0) {return false;}}return true;}
};
暴力代码之所以超时，是因为在每个查询中，直接对范围 [left, right] 逐元素操作，时间复杂度为 O(q×k)，其中 q 是查询的数量，k 是区间长度的平均值。如何在暴力的基础上进行优化呢？
差分数组是一种高效处理区间操作的工具。通过将每次操作分摊到差分数组的起点和终点，避免了逐元素修改，从而极大地提高效率。
差分数组优化：
-
使用一个差分数组 diff 来快速记录区间的减操作：
-
在 diff[left] 加上减操作的次数。
-
在 diff[right + 1] 减去减操作的次数。
-
-
最终通过计算差分数组的前缀和，快速得到对每个位置的累积操作数。
验证零数组：
-
模拟操作时，将 nums[i] 减去当前累积操作数。
-
如果遍历完所有元素都满足条件，则返回 true。
3、代码实现
class Solution {
public:bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();vector<int> diff(n + 1, 0); // 差分数组，大小为 n+1// 构建差分数组for (const auto& query : queries) {int left = query[0], right = query[1];diff[left] -= 1; // 在左端点减 1if (right + 1 < n) {diff[right + 1] += 1; // 在右端点的下一位置加 1}}// 使用差分数组模拟操作int curr_op = 0; // 当前的操作累积值for (int i = 0; i < n; ++i) {curr_op += diff[i]; // 当前位置的操作累积nums[i] += curr_op; // 应用累积操作到 nums[i]if (nums[i] < 0) { nums[i] = 0; // 避免负值}}// 检查是否全部为零for (const auto& num : nums) {if (num != 0) {return false;}}return true;}
};
4、复杂度
时间复杂度：
- 构建差分数组：O(q)，其中 q 是 queries 的数量。
- 应用差分并验证：O(n)，其中 n 是 nums 的长度。
- 总复杂度：O(n+q)。
空间复杂度：
- 差分数组占用 O(n) 的额外空间。