差分数组

前言：

有的时候我们需要对一个数组范围进行多次批量操作，在数组长度很小的时候，直接遍历数组进行操作就可以了。但是当数组长度很大的时候，批量操作很多次效率就会很低，有没有什么快速的方式可以完成这样的操作呢？就是今天要讲到的差分数组了，可以只操作少量的元素来完成批量操作。

介绍

差分数组是在原来的数组上进行用两两作差构造出来一个长度一样的数组(当前的元素减去前面的元素)，叫做差分数组，后续操作就可以在差分数组上完成。

原数组：[ai…an]

差分数组：[a(i), a(i+1) - a(i), a(i+2) - a(i+1)….a(n)- a(n-1)]

diff[i] = \left { arr[0], i = 0 \ arr[i] - arr[i-1], i >=1 \right }

image-20231015214846859

差分数组的性质：

性质1：diff[]从左往右累加a[i] = d[i-1] + d[i]，可以得到原数组。

性质2：原数组区间累加/减（a[i],a[i+1]…a[j]）等于差分数组 d[i] + x并且d[j+1] - x。

特殊情况: j + 1 = 数组长度 , 不需要d[j + 1] - x了，只要d[i] + x。

举个例子：

原数组： [1,0,2,6,7,3]

差分数组：[1,-1,2,4,1,-4]

如果我们要给原数组0-3都加上1，就会变成[1,1,3,7,8,4]，我们操作差分数组就只需要将-1加上1就可以了，差分数组变成[1,0,2,4,1,-1]，然后把差分数组从左到右累加，就变成了[1,1,3,7,8,4]。这样如果是很长的一个数组频繁的累加/减操作，我们都只需要操作两个元素就行了，最后在从左往右累加就可以得出原来数组的结果。

差分数组的典型使用场景:

  • 频繁的区间增加/减少操作

    例如给数组A的[i,j]区间中的每个元素加上c，只需要B[i] += c, B[j+1] -= c

  • 找到数组的区间和

    例如求A数组[i,j]区间元素的和，只需要计算sum(B[i]…B[j])。

  • 解决子数组最大子段和问题

构造差分数组，其前缀和即为原数组的最大段和

  • 解决数组元素出现频率问题

记录差分数组的前缀和，即为原数组中元素出现的频次

总体来说，差分数组适用于需要频繁操作数组区间的场景，可以高效减少操作次数。

实例

LeetCode-2772，这个也是353周赛的第四题。

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
2772. 使数组中的所有元素都等于零
中等
相关标签
相关企业
提示
给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。

你可以对数组执行下述操作 任意次 ：

从数组中选出长度为 k 的 任一 子数组，并将子数组中每个元素都 减去 1 。
如果你可以使数组中的所有元素都等于 0 ，返回  true ；否则，返回 false 。

子数组 是数组中的一个非空连续元素序列。

 

示例 1：

输入：nums = [2,2,3,1,1,0], k = 3
输出：true
解释：可以执行下述操作：
- 选出子数组 [2,2,3] ，执行操作后，数组变为 nums = [1,1,2,1,1,0] 。
- 选出子数组 [2,1,1] ，执行操作后，数组变为 nums = [1,1,1,0,0,0] 。
- 选出子数组 [1,1,1] ，执行操作后，数组变为 nums = [0,0,0,0,0,0] 。
示例 2：

输入：nums = [1,3,1,1], k = 2
输出：false
解释：无法使数组中的所有元素等于 0 。
 

提示：

1 <= k <= nums.length <= 105
0 <= nums[i] <= 106

这一题可以用差分数组来解决，首先要能满足最后元素全部为0，那么不管是原数组还是差分数组第一个元素肯定是0。
如果nums[0] > 0, nums[0]- nums[k]范围的元素都是需要减1来慢慢达成为0的条件, 依次遍历下去
前提是k < n , 要不然不满足题目要求，如果当前元素是i, 那就是i + k < n。
如果nums[0] = 0, 那么就不用管第一个数了，跳过去看下一个数
如果nums[0] < 0, 那肯定没法继续了，不可能达到都为0的情况了

遍历的时候记录一下差分的值sumDiff，最后nums[i] + sumDiff就是实际值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean checkArray(int[] nums, int k) {
      int n = nums.length;
      int sumDiff = 0;
      int[] diff = new int[n + 1];
      for (int i = 0; i < n; i++) {
          sumDiff += diff[i];
          int x = nums[i];
          x += sumDiff;
          // 直接跳过
          if (x == 0) {
              continue;
          }
          // 无法满足条件
          if (x < 0 || i + k > n) {
              return false;
          }
          sumDiff -= x;
          diff[i + k] += x;
      }
      return true;
  }

相关题目

题号 题目 难度
729 我的日程安排表 I 中等
1109 航班预订统计 中等
1094 拼车 中等
2406 将区间分为最少组数 中等
2528 最大化城市的最小供电站数目 困难