3355. 零数组变换 Ⅰ

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;}
};