2251. 花期内花的数目

题目

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

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

示例 1：

输入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

示例 2：

输入：flowers = [[1,10],[3,3]], persons = [3,3,2]
输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

提示：

1 <= flowers.length <= 5 10^4
flowers[i].length == 2
1 <= starti <= endi <= 10^9
1 <= persons.length <= 5 10^4
1 <= persons[i] <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-flowers-in-full-bloom
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

比较常规的思路是：正在开的花的个数 为所有在此时间节点及之前开放的花的个数减去在时间节点之前凋谢的花的个数，来自「这里」。见代码一。

也可以使用差分，见代码二。

代码

代码一 常规思路

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        int n = persons.length;
        int m = flowers.length;
        int[] ans = new int[n];
        int[] start = new int[m];
        int[] end = new int[m];
        for (int i = 0; i < m; i++) {
            start[i] = flowers[i][0];
            end[i] = flowers[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        for (int i = 0; i < n; i++) {
            int s = bsearch(start, persons[i] + 1);
            int e = bsearch(end, persons[i]);
            ans[i] = s - e;
        }
        return ans;
    }
    public int bsearch(int[] nums, int target) {
        int n = nums.length;
        int low = 0;
        int high = n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

代码二 差分

参考「这里」。通过本题学习了差分这个知识点。差分可以看做是前缀和的逆策略，当需要将数组某一区间内的所有值都加上一个值的时候，如果一个个加会比较费时，引入差分数组后只需要更新两个值。这是差分的设计初衷。

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] f : flowers) {
            map.put(f[0], map.getOrDefault(f[0], 0) + 1);
            map.put(f[1] + 1, map.getOrDefault(f[1] + 1, 0) - 1);
        }
        // persons数组中的值在map中不一定存在，后面会还原数组，因此这里可以将不存在的键值添加上，最后直接获取答案就好了
        for (int p : persons) {
            if (!map.containsKey(p)) {
                map.put(p, 0);
            }
        }
        // 还原前缀和数组
        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            sum += entry.getValue();
            int k = entry.getKey();
            map.put(k, sum);
        }
        int[] ans = new int[persons.length];
        for (int i = 0; i < persons.length; i++) {
            ans[i] = map.getOrDefault(persons[i], 0);
        }
        return ans;
    }
}

还可以这么写，个人觉得这么写更好。

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] f : flowers) {
            map.put(f[0], map.getOrDefault(f[0], 0) + 1);
            map.put(f[1] + 1, map.getOrDefault(f[1] + 1, 0) - 1);
        }
        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            sum += entry.getValue();
            int k = entry.getKey();
            map.put(k, sum);
        }
        int[] ans = new int[persons.length];
        // 由于没有向上面那样往map添加不存在的键值，因此需要查找不大于persons[i]的键值，缺失的键值的值一定和这样查找到的值一样
        for (int i = 0; i < persons.length; i++) {
            // 注意可能返回null, 对应来的时刻一朵花没开
            Integer k = map.floorKey(persons[i]);
            if (k != null) {
                ans[i] = map.get(k);
            }
        }
        return ans;
    }
}