差分数组相关知识点以及刷题

差分数组

差分数组是什么？

**举例：**对于数组考虑数组 a=[1,3,3,5,8]，对其中的相邻元素两两作差（右边减左边），得到数组 [2,0,2,3]。然后在开头补上 a[0]，得到差分数组：

​ d=[1,2,0,2,3]

如果对数组进行从左往右累加d中的元素，就对差分数组进行了还原，即还原成了数组a ：

​ a=[1,3,3,5,8]

所以差分数组定义为：差分数组是一个数组，其中每个元素表示原始数组中相邻元素之间的差值。这种数组通常用于解决区间增量更新和查询的问题。

差分数组与前缀和相对应。差分数组通过前缀和求取原始数组，前缀和可以通过差分数组返回原始数组

差分数组怎么计算？

如果有一个原始数组 nums，差分数组 diff 的计算方式如下：

1. 第一个元素 diff[0] 等于原始数组的第一个元素 nums[0]。
2. 对于 i > 0 的每个位置，diff[i] = nums[i] - nums[i - 1]。

举例：nums = [1, 3, 2, 4, 1]的差分数组为：diff = [1, 2, -1, 2, -3]

差分数组有什么用？

通过差分数组，可以在 O(1) 时间内对原始数组的某个区间进行增量更新，而无需修改整个区间的值。对差分数组进行更新时，可以通过修改两个位置的值来实现：

• 对于区间 [left, right] 的增量 val：diff[left] 增加 val，diff[right + 1] 减去 val。
• 举例：
  • 数组nums = [1, 3, 2, 4, 1]，的差分数组为：diff = [1, 2, -1, 2, -3]
  • 对数组nums[1],nums[2],nums[3]都加上10，得到nums' = [1, 13, 12, 14, 1]
  • 对数组进行作差，并在开头补上nums'[0]=nums[0],得到差分数组：diff' = [1, 12, -1, 2, -13]
  • 对比两个差分数组diff = [1, 2, -1, 2, -3]，diff' = [1, 12, -1, 2, -13]可以发现，只有diff[1]和diff[4]发生了变化，这意味着对 nums数组的操作，可以转变成对差分数组 diff的两个数操作。

这种方式在处理大规模数组的增量操作时非常高效，因为它只需要修改差分数组的少数几个元素，然后再根据差分数组重新构建原始数组。

差分数组的性质

性质 1：从左到右累加 diff*中的元素可以得到数组 nums

性质2： 以下两种操作是等价的：

• 把 nums的子数组nums[i], nums[i+1], …, nums[j]都加上x`。
• - 把 diff[i] 增加 x，把 d[j+1] 减少 x。

性质3： 如果nums数组全为0，那么差分数组diff也全为0

利用性质 2，我们只需要 O(1) 的时间就可以完成对 nums 的子数组的操作。最后利用性质 1 从差分数组复原出数组 nums。

Leetcode题目

1094. 拼车

题目：

题目链接：1094. 拼车

题目描述：车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

思路：

1. 初始化一个数组 diff，表示差分数组，用于记录各个站点的乘客数量，站点编号从 1 开始。

2. 对于每个 trip，其中 trip[i]=(c, a, b) 表示有 c 个乘客在 a 站上车，在 b 站下车。对差分数组 nums 区间**[a,b)**，**注意是左开右闭，因为在b站点就下车了。**进行操作：

   • diff[a] += c
   • diff[b] -= c

3. 处理完所有 trips 后，对差分数组 diff 进行前缀计算，即累加数组中的值，得到各个站点的乘客数量。

4. 最后，将各个站点的乘客数量与给定的 capacity 比较，判断是否超载。

   注意： 人为规定站点编号从 1 开始。

代码：

class Solution {public boolean carPooling(int[][] trips, int capacity) {//差分数组：对某段区间可以实现快速的进行同一个操作，再利用前缀和进行恢复数组int ans[] = new int[1010];//计算差分数组for(int i = 0; i < trips.length; i++){int num = trips[i][0];int from = trips[i][1];int to = trips[i][2];ans[from+1] += num;ans[to+1] -= num;}//通过前缀和计算每个时间段的乘客人数for(int i = 1; i <= 1000; i++){ans[i] += ans[i-1];if(ans[i] > capacity) return false;}return true;}
}

差分数组相关题目：

航班预订统计

将区间分为最少组数

字母移位 II

使数组中的所有元素都等于零

最大化城市的最小供电站数目