差分数组
# 差分数组
题目：
370. 区间加法（中等） (opens new window)
1109. 航班预订统计（中等） (opens new window)
1094. 拼车（中等） (opens new window)
之前我们的前缀和数组是在原始数组不变的情况一下，频繁对某个区间的元素进行累加和。现在我们学习一个差分数组，差分数组的主要适⽤场景是频繁对原始数组的 某个区间的元素进⾏增减。
我们先对 nums 数组构造⼀个 diff 差 分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
现在我们就可以通过这个diff差分数组反推我们的原始数组nums:
- 2 = 8 + (-6)
- 6 = 2 + 4
- 3 = 6 + (-3)
- ....
代码逻辑如下：
int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
这样构造构造差分数组diff，就可以快速进行区间增减的操作。
现在如果我们对diff[i]加3之后，就相当于给nums[i..]所有元素都加了3，如果我们想要某个区间i到j的元素全部加3，我们就可以给diff[i]加3之后，还需要再给diff[j+1]减3，意味着把nums[j+1..] 所有元素再减 3。这样我们综合起来就相当于给nums[i..j] 中的所有元素都加 3 了。
代码总结如下：
public class Difference {
/**
* 差分数组
*/
private int[] diff;
/**
* 输入一个初始数组，构建我们的差分数组
*
* @param nums 初始数组
*/
public Difference(int[] nums) {
diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/**
* 给闭区间 [i,j] 增加 val（可以是负数）
*
* @param i i
* @param j j
* @param val 增加的数值
*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
/**
* 返回结果数组
*
* @return 结果数组
*/
public int[] result() {
int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}
注意一下increment方法中的if语句，如果j+1 >= diff.length，说明是对 nums[i] 及以后的整个数组都进⾏修改，那么就不需要再给 diff 数组减 val 了。
# 区间加法
题目：
思路：
这道题在我们上面的思路下就比较简单了，我们只需要把初始数组设置为全0，然后利用刚才的类就可以解决问题。
代码：
public static int[] getModifiedArray(int length, int[][] updates) {
int[] nums = new int[length];
Difference diff = new Difference(nums);
for (int[] update : updates) {
int i = update[0];
int j = update[1];
int val = update[2];
diff.increment(i, j, val);
//for (int item : diff.result()) {
// System.out.println(item);
//}
}
return diff.result();
}
# 航班预订统计
题目：
思路：
这道题其实和上面的一题类似，我们只需要初始化长度为n、全为0的数组，利用差分数组的方法即可解决问题。
代码：
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] nums = new int[n];
Difference diff = new Difference(nums);
for(int[] booking: bookings) {
int i = booking[0] - 1;
int j = booking[1] - 1;
int val = booking[2];
diff.increment(i, j, val);
}
return diff.result();
}
}
class Difference {
private int[] diff;
public Difference(int[] nums) {
diff = new int[nums.length];
diff[0] = nums[0];
for(int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
public int[] result() {
int[] res = new int[diff.length];
res[0] = diff[0];
for(int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}
注意：题目中航班编号是从1开始的，需要把航班编号减去一才能成为数组的索引。
# 拼车
题目：
思路：
这道题我们还是采用差分数组的思想，我们只需要把最后的结果数组遍历一下，看某一个元素是否大于capacity，同时这道题有一个小坑。那就是我们的乘客会下车，那么区间的右边这部分乘客是不在车上的，所以需要减去。
即乘客在车上的区间是 [trip[1], trip[2] - 1]。
代码：
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] nums = new int[1001];
Difference diff = new Difference(nums);
for(int[] trip: trips) {
int val = trip[0];
int i = trip[1];
int j = trip[2] - 1;
diff.increment(i, j, val);
}
int[] res = diff.result();
for(int item : res) {
if (item > capacity) {
return false;
}
}
return true;
}
}
class Difference {
private int[] diff;
public Difference(int[] nums) {
diff = new int[nums.length];
diff[0] = nums[0];
for(int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
public int[] result() {
int[] res = new int[diff.length];
res[0] = diff[0];
for(int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}