差分数组

思路分析

差分数组适用于的场景是频繁对原始数组的某个区间的元素进行增减。

比如给一个输入数组 nums ，然后要求给区间 nums[2..6] 全部加 1，再给区间 nums[3..9] 全部减 3，等等…

最后询问数组的值是多少？

常规思路就是在区间 nums[i..j] 上进行加减操作，就是用一个 for 循环在某区间进行加减操作。这种做法的时间复杂度为 O(N)。如果某个场景对数组的这种操作十分频繁，效率就会十分低下。

这就需要差分数组的技巧了，类似前缀和，构造一个 diff 差分数组，diff[i] = nums[i] - nums[i - 1] ，其中 diff[0] = nums[0] 。

vector<int> diff(nums.size(), 0);
diff[0] = nums[0];
for (int i = 1; i < diff.size(); ++i)
  diff[i] = nums[i] - nums[i - 1];

通过这个差分数组可以反推出原始数组的元素，代码如下：

vector<int> res(diff.size(), 0);
res[0] = diff[0];
for (int i = 1; i < res.size(); ++i)
  res[i] = diff[i] + res[i - 1];

这样构造差分数组 diff ，就可以快速进行区间加减操作。如果相对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3 ，然后让 diff[j + 1] -= 3 即可。原理也比较简单，可以回想由差分数组回推原始数组过程，diff[i] += 3 意味着对于 nums[i..] 所有元素都加 3，然后对 diff[j + 1] - = 3 意味着对 nums[j + 1..] 所有元素减 3，综合起来就是对 nums[i..j] 中的元素都加 3。

只需要花费 O(1) 的时间对 diff 做修改，就相当于对 nums 的整个区间做了修改。多次修改差分数组，然后通过差分数组反推，即可得到原数组被修改后的数组。

可以将差分数组抽象为一个类，包含 increment 方法和 result 方法。代码如下：

class Difference {
private:
    vector<int> diff;
public:
    explicit Difference(vector<int>& nums) {
        diff.resize(nums.size(), 0);
        diff[0] = nums[0];
        for (int i = 1; i < diff.size(); ++i)
            diff[i] = nums[i] - nums[i - 1];
    }
    void increment(int i, int j, int val) {
        /**
         * 对于区间 [i + 1, j] 之间，nums[m] - nums[m - 1] 的值没有变。
         * 对于 i 这个点的元素，因为 + val，所以 nums[i] - nums[i - 1] 不等于原值，需要 + val
         * 对于 j + 1 这个点，因为 j 点值 + val, 所以 nums[j + 1] - nums[j] 不等于原值，需要 -val
         */
        diff[i] += val;
        if (j + 1 < diff.size())
            diff[j + 1] -= val;
    }
    vector<int> result() {
        vector<int> res(diff.size(), 0);
        res[0] = diff[0];
        for (int i = 1; i < res.size(); ++i)
            res[i] = res[i - 1] + diff[i];
        return res;
    }
};

题目讨论

01 区间加法

假设你有一个长度为 n 的数组，初始情况下所有数字均为 0，你将会被给出 k 个更新操作。其中，每个操作会被表示为三元组：[startIndex, endIndex, inc] ，你需要将子数组 A[startIndex...endIndex] （包括 startIndex 和 endIndex ）增加 inc 。请返回 k 次操作后的数组。

可以使用刚才的类来解决：

vector<int> getModifiedArray(int n, vector<vector<int>>& updates) {
  // 初始化数组为 0
  vector<int> diff(n, 0);
  // 构造对象
  Difference df(diff);
  for (auto& array : updates) {
    int i = array[0];
    int j = array[1];
    int val = array[2];
    df.increment(i, j, val);
  }
  return df.result();
}

02 航班预定系统

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

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

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

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/corporate-flight-bookings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

可以翻译一下题目：给定一个长为 n 的数组，初始化为 0。在输入一个 bookings ，里面是三元组 (i, j, val) ，每个三元组的含义就是要求给 nums 数组的闭区间 [i - 1, j - 1] 中所有元素加上 k 。返回最后的 nums 是多少。

因为题目中说下标从 1 开始，而数组下标是从 0 开始的。所以是区间 [i - 1, j - 1] 。

这就满足差分数组的定义。可以直接用刚才定义的类。

class Difference {
private:
  vector<int> diff;
public:
  Difference(vector<int>& nums) {
    diff.resize(nums.size(), 0);
    diff[0] = nums[0];
    for (int i = 1; i < diff.size(); ++i) {
      diff[i] = nums[i] - nums[i - 1];
    }
  }

  void increment(int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < diff.size())
      diff[j + 1] -= val;
  }

  vector<int> result() {
    vector<int> res(diff.size(), 0);
    res[0] = diff[0];
    for (int i = 1; i < res.size(); ++i) {
      res[i] = res[i - 1] + diff[i];
    }
    return res;
  }
};

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
  vector<int> nums(n, 0);
  Difference df(nums);
  for (auto& booking : bookings) {
    int i = booking[0] - 1;
    int j = booking[1] - 1;
    int val = booking[2];
    df.increment(i, j, val);
  }
  return df.result();
}

03 拼车

假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：

• 必须接送的乘客数量；
• 乘客的上车地点；
• 以及乘客的下车地点。

这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false
示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true
示例 3：

输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true
示例 4：

输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/car-pooling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

比如输入：

trips = [[2,1,5],[3,3,7]], capacity = 4

这就不能一次运完，因为在第 3 个上车地点，车的容量为 2，但是有 3 个乘客需要上车。这就超载了。

可以翻译一下题目：trips[i] 表示一组区间的操作，旅客的上下相当于数组的区间加减；只要结果数组中的元素都小于 capacity，就说明可以不超载运输所有旅客。

题目给出了 trip 数组的取值范围：0 <= trips[i][1] < trips[i][2] <= 1000。所以可以初始化数组长度为 1001。代码如下：

class Difference {
private:
    vector<int> diff;
public:
    Difference(vector<int>& nums) {
        diff.resize(nums, 0);
        diff[0] = nums[0];
        for (int i = 1; i < diff.size(); ++i)
            diff[i] = nums[i] - nums[i - 1];
    }
    void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.size())
            diff[j + 1] -= val;
    }
    vector<int> result() {
        vector<int> res(diff.size(), 0);
        res[0] = diff[0];
        for (int i = 1; i < res.size(); ++i)
            res[i] = res[i - 1] + diff[i];
        return res;
    }
};

bool calPooling(vector<vector<int>>& trips, int capacity) {
    vector<int> nums(1001, 0);
    Difference df(nums);
    for (auto& trip : trips) {
        int i = trip[1];
        // 因为在 j 处下车，所以操作区间为[i, j - 1]
        int j = trip[2] - 1;
        int val = trip[0];
        df.increment(i, j, val);
    }
    vector<int> res = df.result();
    for (int num : res) {
        if (num > capacity)
            return false;
    }

}