差分数组
# 差分数组
题目:
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;
}
}