改良空间复杂度的差分数组

发表于 更新于 分类于 Waline：

今天的leetcode每日一题是一道关于差分数组的困难题，其实说是困难题目，但是如果之前知道差分数组的思想，这个题目也不难，甚至是非常明显的差分数组，只不过使用最基础的差分数组的写法在空间上比较浪费，所以需要稍微改良一下。

题目描述如下：

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [startistart_i,endiend_i] 表示第 i 朵花的 花期 从startistart_i 到endiend_i （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间。

请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的数目 。

基本的差分数组思想

这个题目一眼看过去，采用最基础的差分数组的写法，我们就需要声明一个长度为n+1(n为所有flowers中end值的最大值)的数组count，并且每一项都初始化为0，然后遍历flowers数组，对于每一对[start,end][start, end]，我们让count[start]++,count[end+1]−−count[start]++,count[end+1]--，最后在计算每个people的时候，计算差分数组的前缀和即可

但是这个题目的数据有如下限制：

1
2
3
4
5
1 <= flowers.length <= 5 * 104
flowers[i].length == 2
1 <= starti <= endi <= 109
1 <= people.length <= 5 * 104
1 <= people[i] <= 109

改良的差分数组

如果是这样，我们声明的数组就可能很大，所以我们需要考虑是否能够优化这个差分数组的存储。

我们回过头来仔细观察这个差分数组，会发现，其实我们没有必要存储那些从头到尾都没有变化（即flowers数组中从来没出现该项的下标）的项，所以我们可以考虑用map来存储差分数组中变化的项，这样就能节省大量空间。

其次，在对差分数组求前缀和的过程中，我们可以保存下来累计的结果，即先计算出先到的人能看到的花朵数，然后存储下来，再继续计算前缀和到下一个人来的时间点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var fullBloomFlowers = function(flowers, people) {
    const cnt = new Map();
    for (const [start, end] of flowers) {
        cnt.set(start, cnt.has(start) ? cnt.get(start) + 1 : 1);
        cnt.set(end + 1, cnt.has(end + 1) ? cnt.get(end + 1) - 1 : -1);
    }
    const arr = [];
    for (let item of cnt.entries()) {
        arr.push([item[0], item[1]]);
    }
    arr.sort((a, b) => a[0] - b[0]);
    const m = people.length; 
    const indices = new Array(m).fill(0).map((_, i) => i);
    indices.sort((a, b) => people[a] - people[b]);
    let j = 0, curr = 0;
    let ans = new Array(m).fill(0);
    for (const i of indices) {
        while (j < arr.length && arr[j][0] <= people[i]) {
            curr += arr[j][1];
            j += 1;
        }
        ans[i] = curr;
    }
    return ans;
};

其他思路

第 i 到达的时间为 people[i]，假设在 people[i] 时间点之前花开的数目为 x，在 people[i] 时间之前花谢的数目为 y，则在 people[i] 时间点还处于开花状态的数目等于 x−y。我们只需要找到 start≤people[i] 的花朵数目，减去 end<people[i] 的花朵数目即为 people[i] 时间点可以看到花开的数目。 根据以上分析，我们可以单独统计起始时间 start 与结束 end，利用二分查找即可快速查找结果。

首先需要将所有的起始时间 start、结束时间 end 按照从早到晚进行排序；
设第 i 个人到达的时间 people[i]，利用二分查找找到startistart_i≤people[i] 的花朵数目为 x，利用二分查找找到endiend_i<people[i] 的花朵数目为 y，则第 i 个人可以看到的花朵数目为 x−y；

依次遍历并统计每个人的查询结果即可；