一维差分总结

发表于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 4 分钟

适用情景

如果要对数组的多个区间内的元素进行增减操作，可以考虑使用差分数组进行批量化操作。

思路

一般思路

差分数组实质上是前缀和数组的逆过程。

如果要对区间[l, r]内的元素加val，先求差分数组diff，diff数组大小为n+2, 可以避免讨论边界条件，其中diff数组内元素为原数组前后两个元素的差。接下来依次按如下过程操作：

  1. diff[l+1] += val
  2. diff[r+2] -= val

最后对整个差分数组进行求取前缀和，所得的数组即为修改后的数组。

例如，对数组nums = [2, 3, 4, 5]的[1, 3]区间内的所有元素+1，可以使用如下代码进行操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
def f(nums: list[int], l: int, r: int) -> None:
    diff: list[int] = [0] * (len(nums) + 2)
    diff[1] = nums[0]
    # 求差分数组
    for i in range(1, len(nums)):
        diff[i + 1] = nums[i] - nums[i - 1]
    # 修改区间内的值
    diff[l + 1] += 1
    diff[r + 2] -= 1
    # 求前缀和
    for i in range(len(nums)):
        diff[i + 1] += diff[i]
        print(diff[i + 1], end=" ")

输出示例

1
2 4 5 6

等差数列的一维差分

这部分的思想是，对于某个区间内的元素，加上某个等差数列，例如，对某个区间[1, 2, 3, 4]，我们想让该区间的所有元素加上一个等差数列an = 1 + (n - 1) * 1 = n。换句话说，我们期待得到[1+1, 2+2, 3+3, 4+4]，即[2, 4, 6, 8]的结果。那么，我们可以从结果出发，进行推导。

为了简单，假设这样一个数组[0, 0, 0, 0, 0, 0, 0, 0]，设变量s为首项，d为公差，e为末项。[0, s, s+d, s+2d, s+3d, e, 0, 0]是我们的期望。

注意到，对[0, s, d, d, d, d, -e, 0]进行前缀和处理，能得到我们期望的结果。为了方便，我们将这个数组设为arr1。这时候，我们再想，是否有一个差分数组arr2，通过类似diff[l+1] += val diff[r+2] -= val的操作，经过前缀和处理，能得到arr1吗？

这样的数组，是存在的。我们说，差分数组实质上是前缀和数组的逆过程。那么，对于arr1的1号元素s，其实可以通过0 + x = s得到，这里的x是未知数，表示arr2第i号位置的数，这里的i为1。同理，对于arr2的2号元素d，可以通过s + x = d得到，求得x = d - s。同理，可以得到arr2其他位置上的元素。最后，求得arr2 = [0, s, d - s, 0, 0, 0, -e-d, e]。

也就是说，我们只需要求出diff差分数组，接着，按如下步骤操作：

  1. diff[l+1] += s
  2. diff[l+2] += (d - s)
  3. diff[r+2] -= (e + d)
  4. diff[r+3] += e

最后对该差分数组进行两次前缀和处理，就可以得到[0, s, s+d, s+2d, s+3d, e, 0, 0]

例题分析

3355. 零数组变换 I

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

对于每个查询 queries[i]：

  • 在 nums 的下标范围 [li, ri] 内选择一个下标
    子集。

  • 将选中的每个下标对应的元素值减 1。

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

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

解题

这题和1109. 航班预订统计类似，都需要我们在一个数组上的多个区间进行修改操作。因此，我们可以使用差分数组进行分析。

假设我们不考虑排除某一个下标做修改，对于每一个区间，我们对其每个元素都进行修改操作。我们申请一个长度为n+2，全为0的差分数组，对所有区间修改操作结束后，如果差分数组中，存在某个值小于nums[i]，说明修改操作不足以将这个数减为0。因为我们是可以在某一个操作中不选择修改这个元素的，所以如果这个数能变为0，那么差分数组应该满足diff[i] >= nums[i]。

由此，可以写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> diff(n+2, 0);
        for (auto op : queries) {
            int l = op[0], r = op[1];
            diff[l+1]++;
            diff[r+2]--;
        }
        for (int i = 0; i < n; ++i) {
            diff[i+1] += diff[i];
            if (diff[i+1] < nums[i]) {
                return false;
            }
        }
        return true;
    }
};

时间复杂度分析

假设数组长度为n，执行的操作为k，显然，时间复杂度应该为O(n*k)