讲解：labuladong

370. 区间加法（中等）

题目：

 

 思路:

进行多次区间加减。使用差分数组，diff[n]记录num[n]-num[n-1]。这样对于区间[start,end]的加减操作只反映diff[start]+=inc,diff[end+1]-=inc。注意要判断end+1<n，如果超出范围则无需操作

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        //差分数组
        vector<int> diff(length);
        for(int i=0;i<updates.size();++i){
            int start=updates[i][0];
            int end=updates[i][1];
            int inc=updates[i][2];
            //在start+inc
            diff[start]+=inc;
            //判断end+1是否超出范围
            if(end+1<length){
                diff[end+1]-=inc;
            }
        }
        vector<int> ret(length);
        //还原，先取出diff[0]
        ret[0]=diff[0];
        for(int i=1;i<length;++i){
            ret[i]=ret[i-1]+diff[i];
        }
        return ret;
    }
};

 

1109. 航班预订统计（中等）

题目：

 

 

思路：

变形的差分数组。其实仍旧是对于区间进行加减。

这里注意班次为1-n，所以取出的start=bookings[k][0]-1,end也是一样。

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n);
        for(int i=0;i<bookings.size();++i){
            //由于班次为1-n，所以start这里要-1
            int start=bookings[i][0]-1;
            int end=bookings[i][1]-1;
            int inc=bookings[i][2];
            diff[start]+=inc;
            if(end+1<n){
                diff[end+1]-=inc;
            }
        }
        vector<int> ret(n);
        ret[0]=diff[0];
        for(int i=1;i<n;++i){
            ret[i]=ret[i-1]+diff[i];
        }
        return ret;
    }
};

 

1094. 拼车（中等）

题目：

你是一个开公交车的司机，公交车的最大载客量为 capacity，沿途要经过若干车站，给你一份乘客行程表 int[][] trips，其中 trips[i] = [num, start, end] 代表着有 num 个旅客要从站点 start 上车，到站点 end 下车，请你计算是否能够一次把所有旅客运送完毕（不能超过最大载客量 capacity）。

思路;'

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

车站个数最多为 1000，那么我们的差分数组长度可以直接设置为 1001

 

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        //站点最多为1000，所以长度为1001
        int n=1001;
        vector<int> diff(n);
        for(int i=0;i<trips.size();++i){
            int inc=trips[i][0];
            int start=trips[i][1];
            int end=trips[i][2];
            diff[start]+=inc;
            if(end+1<n){
                diff[end+1]-=inc;
            }
        }
        vector<int> ret(n);
        ret[0]=diff[0];
        for(int i=1;i<n;++i){
            ret[i]=ret[i-1]+diff[i];
        }
        //只要过程中每个站点的大小>capacity，就证明超载
        for(int i=0;i<n;++i){
            if(ret[i]>capacity){
                return false;
            }
        }
        return true;
    }
};