​ 在力扣每日一题做到的一系列题目，初次碰到的时候觉得颇有意思，遂记录。

零数组变换 Ⅰ

题面：给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个查询 queries[i]：

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

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

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

​ 题目意思应该不难懂，其实就是对一个数组进行一系列操作看它能不能所有元素全部归零，操作具体记录在一个二维数组，每一个内部的一维数组记录一段下标，范围内的执行一次减一操作。

暴力解法

​ 第一反应是暴力，写出来代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        // 对每个 query 的区间进行直接减操作
        for (const auto& query : queries) {
            int left = query[0];
            int right = query[1];
            for (int i = left; i <= right; ++i) {
                // 将区间 [left, right] 的每个元素减 1
                if (i >= 0 && i < nums.size()) {
                    nums[i]--;
                }
            }
        }

        // 检查所有元素是否小于等于 0
        for (int num : nums) {
            if (num > 0) {
                return false;
            }
        }
        return true;
    }
};

假设 nums.size() = n，queries.size() = m，每个 query 最坏情况可能影响 O(n) 个元素，时间复杂度为O(m*n)。

太暴力了，直接干超时。

差分数组

​ 于是乎我学到了一个叫差分数组的东西，这个东西简直就是为这道题量身定制的，用来高效处理数组区间修改的操作。其核心就是标记你要处理的数据区间的头部和尾部，通过前缀和来还原整个操作。光是看着这段描述就知道效率有多高了。

​ 举个具体的例子吧：

初始数组：

1
a = [0, 0, 0, 0, 0]

操作：

  • 对区间 [1, 3] 加 2
  • 对区间 [2, 4] 加 1
  • 定义一个差分数组为原数组的Size+1，然后在区间操作的left位置+i,right+1的位置-i。

差分数组变化：

1
2
3
4
5
d[1] += 2      // => [0, 2, 0, 0, 0, 0]
d[4] -= 2      // => [0, 2, 0, 0, -2, 0]

d[2] += 1      // => [0, 2, 1, 0, -2, 0]
d[5] -= 1      // => [0, 2, 1, 0, -2, -1]

前缀和还原后：

1
a = [0, 2, 3, 3, 1]

回到我们这道题，操作只有加一和减一，因此也简单了很多，可能会对right有疑问，自己稍微想一下就马上明白原理了，差分数组是很方便多个操作叠加的。

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        // 差分数组，用于记录每个位置被操作了多少次（实际是记录操作“变化量”）
        // 多开一位是为了处理 right+1 的边界情况
        
        vector<int> deltaArray(nums.size() + 1, 0);
        // 遍历所有 query，对每个区间 [left, right] 使用差分技巧标记操作
        for (const auto& query : queries) {
            int left = query[0];
            int right = query[1];
            // 表示从 left 开始要多操作一次
            deltaArray[left] += 1;
            // 表示从 right+1 开始不再操作（撤销这一次加的影响）
            deltaArray[right + 1] -= 1;
        }

        // 计算操作次数的前缀和，得到每个位置实际被操作的总次数
        vector<int> operationCounts;
        int currentOperations = 0;
        for (int delta : deltaArray) {
            currentOperations += delta;
            operationCounts.push_back(currentOperations);
        }

        // 遍历原数组，判断每个位置是否可以被操作到 0 以下
        // 如果某个位置被操作的次数小于它原来的数值，就无法将其归零
        for (int i = 0; i < nums.size(); ++i) {
            if (operationCounts[i] < nums[i]) {
                return false; // 操作次数不足，无法归零
            }
        }

        // 所有元素都能归零，返回 true
        return true;
    }
};

ps:力扣官方题解的源代码

题目其实不难，只是苯人未曾学过差分数组的概念，特此记录

零数组变换 Ⅱ

题面：给你一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri, vali]。

每个 queries[i] 表示在 nums 上执行以下操作：

  • 将 nums 中 [li, ri] 范围内的每个下标对应元素的值 最多 减少 vali。
  • 每个下标的减少的数值可以独立选择。

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

返回 k 可以取到的 最小非负 值，使得在 顺序 处理前 k 个查询后，nums 变成 零数组。如果不存在这样的 k，则返回 -1。

​ 题目意思很好理解，其实就是在上题的基础上让你找到一个最小的操作数使得数组变为零数组，首先可以想到二分查找，在0到queries.size()的范围内去二分查找这个k，对于每个值都检查一遍是否零数组。检查的方式与上题类似，即前缀和检验。

差分数组

这里直接码出苯人的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {        
        int left = 0, right = queries.size() + 1; // 二分查找的范围：[0, queries.size()]
        int mid = 0;
        // 二分查找最小的 k，使得前 k 个 queries 能将 nums 变成全 0
        while (left < right) {
            mid = (left + right) / 2;
            // 如果当前前缀 k 可行（能把 nums 清零），尝试更小的 k
            if (check(mid, nums, queries)) {
                right = mid;
            } else {
                // 否则尝试更大的 k
                left = mid + 1;
            }
        }
        // 若 left 超出 queries 范围，说明无法清零；否则返回合法的最小 k
        return (left <= queries.size()) ? left : -1;
    }
    // 检查前 k 个 queries 是否能将 nums 全部变为 0
    bool check(int k, vector<int> nums, vector<vector<int>> queries) {
        // 差分数组，用于记录每个位置最多可减少的总量（初始化为 0）
        vector<int> deltaArray(nums.size() + 1, 0);
        // 构建差分数组：将前 k 个 query 的影响加入
        for (int i = 0; i < k; ++i) {
            int l = queries[i][0], r = queries[i][1], val = queries[i][2];
            deltaArray[l] += val; // 区间加 val 的差分起点
            if (r + 1 < deltaArray.size()) {
                deltaArray[r + 1] -= val; // 区间结束后的差分终点
            }
        }
        int cur = 0; // 当前累计可减总量
        for (int i = 0; i < nums.size(); ++i) {
            cur += deltaArray[i]; // 差分数组恢复前缀和（累计可减量）
            // 如果当前可减量不足以将 nums[i] 变为 0，返回 false
            if (nums[i] > cur) return false;
        }
        // 所有元素都可以被削减为 0，返回 true
        return true;
    }
};

也是比较暴力的解法，时间复杂度在O((m+n)*log n)，n是nums的长度，m是queries的长度，空间复杂度为O(n)，所幸能过。

双指针

这里看到力扣题解有个很不错的解法，即顺序遍历 nums，每遇到一个值不足以被当前操作减为 0 的位置时，就继续执行 queries，直到能满足当前值为止。

其实就是从nums的元素逐一检查，找到能够归零的最小k值，k和差分数组是逐渐变大的，这样能够获得一个较好的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        // 差分数组，deltaArray[i] 表示 nums[i] 的差分影响（累积能减的量）
        vector<int> deltaArray(n + 1, 0);
        int operations = 0; // 当前下标位置已经累积的最大可减总量
        int k = 0; // 当前 query 用到的位置（表示前 k 个 query 被用了）
        // 遍历每个 nums[i]
        for (int i = 0; i < n; ++i) {
            // 累积前缀和，还原第 i 个位置实际可减总量
            operations += deltaArray[i];
            // 如果当前可减量不足以让 nums[i] 归零
            while (k < queries.size() && operations < nums[i]) {
                int left = queries[k][0];
                int right = queries[k][1];
                int value = queries[k][2];
                // 将当前 query 的区间加 val 用差分数组表示
                deltaArray[left] += value;
                if (right + 1 <= n) {
                    deltaArray[right + 1] -= value;
                }
                // 如果当前 query 覆盖到 i，就立即加到 operations 中（贪心加快）
                if (left <= i && i <= right) {
                    operations += value;
                }
                k++; // 使用了一个 query
            }
            // 若用尽 query 仍不能清零当前元素
            if (operations < nums[i]) {
                return -1;
            }
        }
        // 所有 nums[i] 都能归零，返回用掉的 query 数 k
        return k;
    }
};

复杂度分析

  • 时间复杂度：O(m+n)，其中 n 是 nums的长度，m 是queries的长度。
  • 空间复杂度：O(n)。

零数组变换 Ⅲ

题面：给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [li, ri] 。

每一个 queries[i] 表示对于 nums 的以下操作：

  • 将 nums 中下标在范围 [li, ri] 之间的每一个元素 最多 减少 1 。
  • 坐标范围内每一个元素减少的值相互 独立 。

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

请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组 。如果无法将 nums 变为一个 零数组 ，返回 -1 。

题目开始看着有些复杂了，第一眼时贪心或者dp，但感觉有瑕疵，其实我总觉得贪心的性质经常不够严谨，但是就是能过。

这里我先用了很常规的思路：建立一个差分数组，然后和原数组比较，如果不能归零则返回-1，再写一个数组记录差分数组和原数组的差值，遍历queries，如果其中的l到r的位置都大于0，那么这个数组就是可以删除的，然后就把这个给删了。

但是没能ac，通过了708/824

原因在于这个顺序遍历，没有找到最优的删除顺序，比如一个queries等于另外两个之和，明明可以删两个但是只删了一个。这里的想法是优先找到最小的queries去删除，但是实际上会出现很多问题，比如这个组现在不能删但是之后能删，总之这个顺序敏感不好处理。

于是观察题解，题解用到的是贪心加优先队列，跟我的思路解法正好相反:

​ 首先我们考虑 nums 中下标为 0 的元素，若 nums[0]>0，我们肯定要在queries中找到至少 nums[0] 个左端点为 0 的元素保留，这样才能让 nums[0] 降为 0。
​ 那么选哪 nums[0] 个呢？贪心地考虑，是选右端点最大的那些。选完之后，我们考虑 nums[1]。前一步操作选出的部分元素，可能会有不包含下标 1 的，我们需要将它去掉。这一部分也可以用差分数组deltaArray来完成。此时累积的操作数可能不能将 nums[1] 降为 0，我们仍然要像上一步一样，选出部分 queries 的元素。
​ 这个时候我们可以从未被挑选的元素中，选出左端点 ≤1 的部分中，选出右端点最大的一部分，直到操作数满足 nums[1] 可以降到 0。这个计算过程，可以由一个优先队列 heap 来完成。我们不停地遍历 nums 的过程中，将对应下标为左端点的 queries 的右端点放入 heap 中，并且当操作数不够时，从 heap 中不停取出最大的右端点，直到操作数满足要求。遍历完成后，heap 的长度就是可以删除的 queries。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        sort(queries.begin(), queries.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });
        
        priority_queue<int> heap;
        vector<int> deltaArray(nums.size() + 1, 0);
        int operations = 0;
        for (int i = 0, j = 0; i < nums.size(); ++i) {
            operations += deltaArray[i];
            while (j < queries.size() && queries[j][0] == i) {
                heap.push(queries[j][1]);
                ++j;
            }
            while (operations < nums[i] && !heap.empty() && heap.top() >= i) {
                operations += 1;
                deltaArray[heap.top() + 1] -= 1;
                heap.pop();
            }
            if (operations < nums[i]) {
                return -1;
            }
        }
        return heap.size();
    }
};

复杂度分析

  • 时间复杂度：O(n+m×log m)，其中 n 是 nums的长度，m 是 queries 的长度。
  • 空间复杂度：O(n+m)。