LeetCode 370/1109/1094 差分数组题解，解决差分数组类型的多道同类题。

差分数组

技巧学习

与 前缀和 类似，差分数组是一种对数组预处理的技巧。

定义：

1

diff[i]=num[i]-num[i-1]

即差分数组 diff 中存储原始数组每一项与前一项之差。

同理：

1
2

num[i]=diff[i]+num[i-1] 
num[0]=diff[0]

我们就可以用差分数组还原 原始数组。

适用于数组范围同一增减操作的情况。

本文通过差分数组基础模板与几道题目来感受、理解其精髓、运用。

模板代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

public class DiffArray {
    /**
     * 差分数组
     */
    int[] diff;

    public DiffArray(int n) {
        assert n > 0;
        diff = new int[n];
    }

    public DiffArray(int[] nums) {
        assert nums != null;

        diff = new int[nums.length];
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /**
     * 对 [from,to] 范围数据 +val 操作
     * 相比直接操作原数组，这里操作为 O(1) 复杂度
     *
     * @param from 左闭区间
     * @param to   右闭区间
     * @param val  操作值
     */
    public void rangeOp(int from, int to, int val) {
        // [from,end] 均做了+val操作
        diff[from] += val;
        if (to + 1 < diff.length) {
            // 如果 to+1 未越界，则对 [to+1,end] 减去val，做抵消
            diff[to + 1] -= val;
        }
    }

    /**
     * 根据差分数组还原原始数组
     * 部分题型可以使用diff[]，可以考虑不创建新的数组返回
     */
    public int[] diff2Origin() {
        int[] originArr = new int[diff.length];
        originArr[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            originArr[i] = originArr[i - 1] + diff[i];
        }
        return originArr;
    }

}

题目

370. 区间加法

https://leetcode.cn/problems/range-addition/

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k​​​​​​​ 个更新的操作。

其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex … endIndex]（包括 startIndex 和 endIndex）增加 inc。

请你返回 k 次操作后的数组。

粗暴解

在没有学习过差分数组的理念前，我一般只能想到粗暴解。

思路

我们直接遍历updates，然后以暴力迭代的方式再内部循环。

直接看下代码吧！

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    static class BF {
        public int[] getModifiedArray(int n, int[][] updates) {
            int[] arr = new int[n];

            for (int[] update : updates) {
                int startIdxInclusive = update[0];
                int endIdxInclusive = update[1];
                int inc = update[2];
                for (int i = startIdxInclusive; i <= endIdxInclusive; i++) {
                    arr[i] += inc;
                }
            }

            return arr;
        }
    }

复杂度分析

时间

循环套循环，O(n^2)时间复杂度。

很明显这里是需要优化的！

空间

无额外空间占用，空间复杂度O(1)。

差分数组优化

思路

可以看到暴力解法的时间消耗主要是因为内部循环k个元素。

而使用差分数组的解法，我们修改diff[]，内部仅需O(1)复杂度。还原为原始数组也仅需O(n)。

整体复杂度O(n)。相比暴力解，差分数组的预处理提高了效率！

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

static class DiffArray {

      public int[] getModifiedArray(int n, int[][] updates) {
            // 差分数组， diff[i]表示 nums[i]-nums[i-1]
            int[] diff = new int[n];
            // 对差分数组操作
            for (int[] update : updates) {
                  int startIdxInclusive = update[0];
                  int endIdxInclusive = update[1];
                  int inc = update[2];

                  diff[startIdxInclusive] += inc;
                  if (endIdxInclusive + 1 < n) {
                        diff[endIdxInclusive + 1] -= inc;
                  }
            }
            // 根据差分数组还原 原数组
            // int[] arr = new int[n];
            // arr[0] = diff[0];
            for (int i = 1; i < n; i++) {
                  diff[i] = diff[i - 1] + diff[i];
            }
            return diff;
      }
}

复杂度分析

时间

如上分析，O(n)时间复杂度。

空间

无额外空间占用，空间复杂度O(1)。

1109. 航班预订统计

https://leetcode.cn/problems/corporate-flight-bookings/

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

差分数组

思路

本题没有太抽象的设计，比较容易能匹配到差分数组的概念上。

  • n个航班，对应数组n个元素
  • bookings 对应若干个范围操作
    • first 对应左闭区间
    • last 对应右闭区间
    • seats 对应我们的rangeOpValue
  • answer 即原始数组

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

static class DiffArr {
      public int[] corpFlightBookings(int[][] bookings, int n) {
            int[] diff = new int[n];
            for (int[] booking : bookings) {
                  // [first,last]上+=seats
                  int first = booking[0] - 1;
                  int last = booking[1] - 1;
                  int seats = booking[2];
                  diff[first] += seats;
                  if (last + 1 < n) {
                        diff[last + 1] -= seats;
                  }
            }
            for (int i = 1; i < n; i++) {
                  diff[i] = diff[i - 1] + diff[i];
            }
            return diff;
      }
}

复杂度分析

时间

使用差分数组处理范围操作仅需O(n)，还原原始数组也需O(n)，整体O(n)时间复杂度。

空间

无额外空间占用，空间复杂度O(1)。

1094. 拼车

https://leetcode.cn/problems/car-pooling/

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

差分数组

思路

这道题相对来说我没有那么快想到差分数组。

我的思路是： 对于给定的trips，我们可以对他处理、排序：

  • 将 [numPassengersi, fromi, toi] 处理为 [point,num] 的格式，上车人数对应正数，下车人数对应负数；
  • 数组整体按point从小到大排序；
  • 依次计算每个point我们需要的车负载；

到这里，回想到了 字节 根据日志求用户在线峰值与持续时长 题解 应该也可以用同样的思路。

我们把point抽象理解为车站，根据题干：

1

0 <= fromi < toi <= 1000

我们可以开辟一个[0,1000]长度1001的数组，来使用差分数组实现。

关键点： 原数组存储每个站实际载客人数，差分数组存每个站相比前站的增量。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

static class DiffArr {
      public boolean carPooling(int[][] trips, int capacity) {
            // 原数组存储每个站实际载客人数，差分数组存每个站相比前站的增量
            int[] diff = new int[1001];
            for (int[] trip : trips) {
                  int numPassengers = trip[0];
                  int from = trip[1];
                  int to = trip[2];
                  diff[from] += numPassengers;
                  if (to < 1001) {
                        diff[to] -= numPassengers;
                  }
            }
            int maxLoad = diff[0];
            for (int i = 1; i < 1001; i++) {
                  if (maxLoad > capacity) {
                        return false;
                  }
                  maxLoad += diff[i];
            }
            return true;
      }
}

复杂度分析

时间

整体O(n)时间复杂度。

空间

diff[]为额外空间，空间复杂度O(1001)。