差分数组

定义

差分数组是把原数组中后一个元素减前一个元素的差构成一个新的数组，作为辅助数组使用；

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];

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

比如想对[1, 3]范围的元素都加1时，只需用diff[1] += 1``diff[4] -= 1;

例题

预定日程

思路

在每次book的时候:

• start处++,代表时间推进到start的时候,多了一个预定任务；
• end处–,代表时间推进到end的时候预定任务减少一个;

然后整体遍历一遍有序的map表，找到累计的最大预定次数。

class MyCalendarThree {
public:
    MyCalendarThree() {

    }
    
    int book(int start, int end) {
        int ans = 0;
        int maxBook = 0;
        cnt[start]++;
        cnt[end]--;
        for (auto &[_, freq] : cnt) {
            //根据差分数组还原原来数组的值，用于下面求最大值
            maxBook += freq;
            //更新最大预定值；
            ans = max(maxBook, ans);
        }
        return ans;
    }
private:
    //构建差分数组
    map<int, int> cnt;//不能是umap
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(start,end);
 */