LeetCode-732. 我的日程安排表 III，差分数组

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。
给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。
实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。
MyCalendarThree() 初始化对象。int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/my-calendar-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

背景

差分数组是把原数组中后一个元素减前一个元素的差构成一个新的数组，作为辅助数组使用。如下图所示：

diff[0] = nums[0];
diff[1] = nums[1] - nums[0];
diff[2] = nums[2] - nums[1];
...

nums[0] = diff[0];
nums[1] = diff[1] + nums[0] =  diff[0] + diff[1];
nums[2] = nums[1] + diff[2] =  diff[0] + diff[1] + diff[2];

根据差分数组各项的前缀和，即可还原出原数组各值，查分数组常用于对区间内元素值到统一修改。

应用

假如把 nums 数组中 [0,3] 范围到元素值都加 2：

常规方法：

for( int i =0;i < 4;++i)
{
    
    nums[i] += 2;
}

差分方法：

diff[0] += 2;// 0 往后到值全部加 2
diff[4] -= 2;// 4 往后到值全部减 2

题目分析

有一个数组初始值全部为 0 ，每次调用 book 方法都把 [start,end) 范围内到元素加 1，并返回当前数组到最大值。

直接构建差分数组，更改区间值后再用前缀和还原出原数组即可。

#### 代码示例
class MyCalendarThree {
    
public:
    MyCalendarThree() {
    

    }
    
    int book(int start, int end) {
    
        diff[start]++;// start 开始的值都加 1
        diff[end]--;// end 开始的值都减 1
        int res = 0;
        int cur = 0;
        for( auto & kv : diff )
        {
    
            cur += kv.second;//前缀和还原原数组值
            res = max(res,cur);
        }
        return res;
    }
private:
    map<int,int> diff;//差分数组
};