他跟我们前一次学过的前缀数组有些类似,都是通过new一个数组,对他进行操作,得到我们想要的差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。// 差分数组工具类 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]; } } // 给闭区间 [i, j] 增加 val可以是负数 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; } }力扣第 1109 题「航班预订统计」class Solution { public int[] corpFlightBookings(int[][] bookings, int n) { // nums 初始化为全 0 int[] nums new int[n]; // 构造差分解法 Difference df new Difference(nums); for (int[] booking : bookings) { // 注意转成数组索引要减一哦,因为航班对应的是1,2,3,换到索引要-1对齐 int i booking[0] - 1; int j booking[1] - 1; int val booking[2]; // 对区间 nums[i..j] 增加 val df.increment(i, j, val); } // 返回最终的结果数组 return df.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]; } } // 给闭区间 [i, j] 增加 val可以是负数 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.先构建原数组2.new差分数组–原数组当前-前一个3.把要加的用for抽离出来,注意是否要-1(情景)4.把抽离出来的各个数,给差分数组进行运算(死的)5.new一个结果数组,存放差分数组运算完完后的内容.力扣第 1094 题「拼车」class Solution { public boolean carPooling(int[][] trips, int capacity) { // 最多有 1000 个车站 int[] nums new int[1001]; // 构造差分解法 Difference df new Difference(nums); for (int[] trip : trips) { // 乘客数量 int val trip[0]; // 第 trip[1] 站乘客上车 int i trip[1]; // 第 trip[2] 站乘客已经下车 // 即乘客在车上的区间是 [trip[1], trip[2] - 1] int j trip[2] - 1; // 进行区间操作 df.increment(i, j, val); } int[] res df.result(); // 客车自始至终都不应该超载 for (int i 0; i res.length; i) { if (capacity res[i]) { 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]; } } // 给闭区间 [i, j] 增加 val可以是负数 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.乘客下车在5,所以他只是1-4在车上2.最后得到结果数组要进行for循环的遍历判断