认识和使用差分数组

今天在做力扣1450题时，碰到没使用过的差分数组，在这里做一个学习笔记～

1.什么是差分数组？

从字面上解释，差分数组就是记录一个数组的前后元素之差的数组，例如：

有数组nums的内容如下：

那么数组nums的差分数组diff就是：

数组diff的长度和原数组nums一样，其中diff[0]默认为nums[0]，其它diff[i] = nums[i] - nums[i-1]。

（1）差分数组的特点一：

当我们需要在长度很大的原数组的某个区间做频繁的统一运算操作时，可以不操作原数组，而是直接计算其差分数组以提高效率。举个简单的例子，现在需要将上面数组nums的[1, 3]区间元素都累加2，则结果如下：

所以对原数组某个区间的操作只会影响差分数组中两个元素的值，如果区间是[i,j]，那么只会影响差分数组的i和j+1两个元素

（2）差分数组的特点二：

d[i] = f[0] + f[1] + ... + f[i]

即用差分数组的前i项和可以求得原数组的第i个元素的值！

nums[3] = 7 = diff[0] + diff[1] + diff[2] + diff[3] = 2 + 4 - 3 + 4 = 7

2.使用差分数组

力扣1450道题，给了一组学生做作业的时间段，求在给定时刻正在做作业的学生个数。

以下是我对用差分数组解题的思路：

（1）用数组count[]记录每个时刻正在做作业的学生个数，题目求count[i]，初始条件count[i] = 0

（2）用数组diff[]表示count[]的差分数组，初始条件diff[i] = 0

（3）循环给定时间段数组，

        如果是操作原数组：对于[starttime, endTime]区间的时刻i，都有count[i]+1；

        如果是操作差分数组：对于[starttime, endTime]区间的时刻i，都有diff[startTime]+1，diff[endTime+1]-1;

（4）因为是用差分数组解题，所以直接操作差分数组，然后求查分数组的前缀和即可

代码如下：

class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int len = startTime.length;
        int max = Arrays.stream(endTime).max().getAsInt();
        if (queryTime > max) {
            return 0;
        }
        // 因为差分数组的最大下标是max+1，所以这里差分数组的长度应该是max+2
        int[] diff = new int[max+2];
        for(int i=0; i
            diff[startTime[i]]++;
            diff[endTime[i]+1]--;
        }
        int ans = 0;
        for(int i=0; i<= queryTime; i++) {
            ans += diff[i];
        }
        return ans;
    }
}