网站开发项目进度安排新东方留学机构官网
差分数组
差分数组是什么？
**举例：**对于数组考虑数组 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 的计算方式如下：
- 第一个元素
diff[0]等于原始数组的第一个元素nums[0]。 - 对于
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
思路：
-
初始化一个数组
diff，表示差分数组，用于记录各个站点的乘客数量，站点编号从 1 开始。 -
对于每个
trip，其中trip[i]=(c, a, b)表示有c个乘客在a站上车，在b站下车。对差分数组nums区间**[a,b)**，**注意是左开右闭，因为在b站点就下车了。**进行操作：diff[a] += cdiff[b] -= c
-
处理完所有
trips后，对差分数组diff进行前缀计算，即累加数组中的值，得到各个站点的乘客数量。 -
最后，将各个站点的乘客数量与给定的
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
使数组中的所有元素都等于零
最大化城市的最小供电站数目