当前位置：首页 > article >正文

差分数组解析

article 2025/2/22 2:24:55

差分数组解析

差分数组是一种处理区间更新问题的高效数据结构。其核心思想是通过记录区间的“变化量”，从而将多次区间更新转化为常数时间操作，最终通过前缀和得到结果。

差分数组介绍

基本概念：

差分数组：给定一个数组 arr，我们定义一个差分数组 diff，它记录的是相邻元素的差值，即 diff[i] = arr[i] - arr[i-1]。通过差分数组，我们可以快速处理区间更新。
区间更新：如果我们想对数组 arr 的某个区间 [l, r] 内的每个元素都增加一个常数值 x，传统的方法是直接遍历该区间，进行逐个更新。但使用差分数组，我们只需要在 diff[l] 处增加 x，并在 diff[r+1] 处减少 x（如果 r+1 不越界）。最后通过计算差分数组的前缀和，我们就可以得到更新后的数组。

差分数组的工作流程：

初始化差分数组：
- 假设原数组 arr 的长度为 n，那么差分数组 diff 的长度也为 n，且所有元素初始化为0。
区间增量操作：
- 对于更新区间 [l, r]，将 diff[l] 加上增量 x，并将 diff[r+1] 减去增量 x（如果 r+1 在数组范围内）。
计算前缀和：
- 通过对差分数组 diff 进行前缀和累加，恢复出更新后的原数组。
复杂度分析：
- 区间更新：O(1)
- 最终恢复结果（通过前缀和）：O(n)

差分数组适合用于需要对数组进行多次区间更新（加法、减法等）的场景，尤其是在我们需要在查询时获得更新后的值时，能大大提高效率。

举例说明：区间更新

假设我们有原数组 arr = [1, 2, 3, 4, 5]，并且我们要对区间 [1, 3] 进行加 10 操作。

初始化差分数组

首先，构造一个差分数组 diff，并将所有元素初始化为 0：

arr = [1, 2, 3, 4, 5]
diff = [0, 0, 0, 0, 0]   // 初始化差分数组

对区间 [1, 3] 加 10

通过差分数组的方式，更新区间 [1, 3]：

在 diff[1] 加上 10，表示从位置 1 开始，所有元素加 10。
在 diff[4] 减去 10，表示从位置 4 开始，所有元素恢复。

此时，diff 数组变为：

diff = [0, 10, 0, 0, -10]

恢复原数组

通过对差分数组进行前缀和，恢复原数组的值：

arr[0] = diff[0] = 0
arr[1] = diff[0] + diff[1] = 0 + 10 = 10
arr[2] = diff[0] + diff[1] + diff[2] = 0 + 10 + 0 = 10
arr[3] = diff[0] + diff[1] + diff[2] + diff[3] = 0 + 10 + 0 + 0 = 10
arr[4] = diff[0] + diff[1] + diff[2] + diff[3] + diff[4] = 0 + 10 + 0 + 0 - 10 = 0

最终，更新后的 arr 数组为 [1, 12, 13, 14, 5]，符合我们对区间 [1, 3] 加 10 的要求。

1109. 航班预订统计

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

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

示例 1：

输入：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]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

class Solution {
public:
    //  差分数组
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> result(n,0);
        vector<int> diff(n,0);
        for(int i=0; i<bookings.size(); i++){
            int a = bookings[i][0];
            int b = bookings[i][1];
            int k = bookings[i][2];
            if(a<=n&&a>0){
                diff[a-1]+=k;
            }
            if(b<n&&b>0){
                diff[b]-=k;
            }
        }
        result[0]=diff[0];
        for(int i=1; i<n; i++){
            result[i]=result[i-1]+diff[i];
        }
        return result;
    }
};

1094. 拼车

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

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

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

示例 1：

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

示例 2：

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

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int bmax = 0;
        for(auto&trip:trips){
            bmax = max(bmax,trip[2]);
        }

        vector<int> diff(bmax+1, 0);

        for(int i=0; i<trips.size(); i++){
            int p = trips[i][0];
            int a = trips[i][1];
            int b = trips[i][2];
            diff[a]+=p;
            if(b<=bmax+1) {
                diff[b]-=p;
            }
        }
        int count=0;
        for(int i=0; i<=bmax; i++){
            count+=diff[i];
            if(count>capacity){
                return false;
            }
        }
        return true;
    }
};