【LBLD】差小而美的算法技巧：差分数组

差分数组

差分数组的第 i 个元素存储原数组第 i 个元素和第 i-1 个元素的差值，其中，差分数组的首元素的值 diff[0] 为原数组首元素的值 nums[0]。

1109.航班预订统计

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto booking : bookings) {
            diff[booking[0]-1] += booking[2];
            if (booking[1] < n) {
                diff[booking[1]] -= booking[2];
            }
        }
        for (int i=1; i<n; i++) {
            diff[i] = diff[i-1] + diff[i];
        }
        return diff;
    }
};

1094.拼车

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001, 0);
        for (auto trip : trips) {
            diff[trip[1]] += trip[0];
            diff[trip[2]] -= trip[0];
        }
        int passengers = 0;
        for (int i=0; i<1001; i++) {
            passengers += diff[i];
            if (passengers > capacity) {
                return false;
            }
        }
        return true;
    }
};