leetcode1109. 航班预订统计

1109. 航班预订统计

这道题使用暴力解法，如果数据比较多，first 和 second跨度比较大时会超时。比如下面这个暴力解：

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n,0);
        int size = bookings.size();
        for(int i = 0;i < size;i++){
            for(int j = bookings[i][0]; j <= bookings[i][1];j++){
                res[j-1] += bookings[i][2];
            }
        }
        return res;
    }
}

正确解：

对于一个「将区间 [l,r] 整体增加一个值 v」操作，我们可以对差分数组 c 的影响看成两部分：

对 c[l] += v：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标大于等于 l 的位置都增加了值 v；
对 c[r+1]−=v：由于我们期望只对 [l,r] 产生影响，因此需要对下标大于 r 的位置进行减值操作，从而抵消“影响”。
对于最后的构造答案，可看做是对每个下标做“单点查询”操作，只需要对差分数组求前缀和即可。

作者：宫水三叶

class Solution {
public:
    //当我们希望对原数组的某一个区间[l,r]施加一个增量inc时，可对其差分数组d做出操作：
    //d[l]增加inc,d[r+1]减少inc,然后再通过差分数组还原数组。
    //特别注意，当r = 右边界时，无需修改d[有边界]。
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n,0);
        for(const auto &booking : bookings){
            res[booking[0]-1] += booking[2];
            if(booking[1] < n)  res[booking[1]] -= booking[2];
        }
        
        for(int i = 1;i < n;i++)  res[i] += res[i-1];
        return res;
    }
};

/*
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n,0);
        int size = bookings.size();
        for(int i = 0;i < size;i++){
            res[bookings[i][0]-1] += bookings[i][2];
            if(bookings[i][1] < n)  res[bookings[i][1]] -= bookings[i][2];
        }

        for(int i = 1;i < n;i++)  res[i] += res[i-1];
        return res;
    }
};*/