LeetCode 1109 LeetCode 370 差分数组算法技巧

LeetCode370 区间加法

1. 思路分析

   1. 使用差分数组的解题技巧

   2. 差分数组：主要适用场景是频繁对原始数组的某个区间的元素进行增减；类似于前缀和构造的prefix数组，我们构造一个差分数组diff。

      diff[i] = nums[i] - nums[i - 1]

   3. 示意图

   4. 运用差分数组进行区间增删的操作

      若对nums[i…j]增(删) value ：

      则diff[i] += value，即nums[i…]增加了value

      之后diff[j+1] -= value，即对nums[j…]减少了value，综合起来就是没有变化

   5. 返回结果数组

      根据差分数组构造结果数组result：result[0] = diff[0]; result[i] = result[i - 1] + diff[i]

2. 代码实现

   class Solution {
       private int[] diff;
       public int[] getModifiedArray(int length, int[][] updates) {
           int[] nums = new int[length];
           difference(length, nums);
           for (int[] update : updates) {
               int i = update[0];
               int j = update[1];
               int value = update[2];
               increment(i, j, value);
           }
           return result();
       }
   
       //构造差分数组
       void difference(int length, int[] nums) {
           diff = new int[length];
           diff[0] = nums[0];
           for(int i = 1; i < length; i++) {
               diff[i] = nums[i] - nums[i-1];
           }
       }
   
       //根据题意对区间元素进行增减
       void increment(int i, int j, int value) {
           diff[i] += value;
           if (j + 1 < diff.length) {
               diff[j + 1] -= value;
           }
       }
   
       //根据差分数组构建结果数组返回
       int[] result() {
           int[] result = new int[diff.length];
           result[0] = diff[0];
           for (int i = 1; i < diff.length; i++) {
               result[i] = result[i - 1] + diff[i];
           }
           return result;
       }
   }
   

LeetCode1109 航班预订统计

1. 思路分析：使用差分数组
2. 代码实现：与上同，注意i和j要减1

LeetCode1094 拼车

1. 思路分析：使用差分数组，trips[i] 代表着一组区间操作，旅客的上车和下车就相当于数组的区间加减；只要结果数组中的元素都小于 capacity，就说明可以不超载运输所有旅客。

   1. 根据给出的数值范围0 <= fromi < toi <= 1000，可以知道该车从0站台到1000站台，即最多有1001个站台，则diff.length = 1001;

   2. 构造差分数组

      根据trip读取每条旅程信息，trip[1]站有trip[0]个乘客上车；判断trip[2] 是否大于 diff.length(用trip[2] 而不是用trip[2] +1的原因是trip[2]时乘客下车)，若trip[2] >= diff.length，则说明到最后一站，不做处理，否则trip[2]站有trip[0]个乘客下车，即乘客在车上的区间为[trip[1], trip[2] - 1]

   3. 判断是否超载

      根据 差分数组的前缀和就是原数组元素 这一性质，对diff求前缀和并判断是否大于capacity即可，注意在此之前要判断diff[0]是否超载，即初始站是否超载

2. 代码实现

   class Solution {
       public boolean carPooling(int[][] trips, int capacity) {
           int[] diff = new int[1001];
           for (int[] trip : trips) {
               diff[trip[1]] += trip[0];
               if (trip[2] < diff.length) {
                   diff[trip[2]] -= trip[0];
               }
           }
   
           if (diff[0] > capacity) return false;
           //检查到每一站的乘客是否大于容量
           for (int i = 1; i < diff.length; i++) {
               diff[i] += diff[i-1];
               if (diff[i] > capacity) {
                   return false;
               }
           }
           return true;
       }
   }