豆包 LeetCode 2251. 花期内花的数目 public int[] fullBloomFlowers(int[][] flowers, int[] people)

LeetCode 2251 解题思路 最优代码这道题是经典的差分 排序 二分问题非常高频最优解法时间复杂度O(n log n m log n)。题目理解flowers[i] [start, end]花从start到end每天都开放people[i]人到达的时间要求返回每个人到达时正开放的花有多少朵核心思路最优解法把花期拆分成两个事件花开start位置 1花谢end 1位置 -1因为 end 当天还开着对所有时间点排序对 people 数组排序保留原始下标用双指针/前缀和 二分快速统计每个人到达时的花数完整 Java 代码importjava.util.*;classSolution{publicint[]fullBloomFlowers(int[][]flowers,int[]people){intnflowers.length;intmpeople.length;// 1. 收集花开、花谢时间int[]startsnewint[n];int[]endsnewint[n];for(inti0;in;i){starts[i]flowers[i][0];ends[i]flowers[i][1];}// 2. 排序Arrays.sort(starts);Arrays.sort(ends);// 3. 对每个人二分查找 time 的花开数量 - 小于 time 的花谢数量int[]resnewint[m];for(inti0;im;i){inttimepeople[i];// 花开 time有多少朵intbloomupperBound(starts,time);// 花谢 time有多少朵intfalllowerBound(ends,time);res[i]bloom-fall;}returnres;}// 找 target 的最后一个位置 1总数privateintupperBound(int[]arr,inttarget){intl0,rarr.length;while(lr){intmidl(r-l)/2;if(arr[mid]target){lmid1;}else{rmid;}}returnl;}// 找 target 的第一个位置总数privateintlowerBound(int[]arr,inttarget){intl0,rarr.length;while(lr){intmidl(r-l)/2;if(arr[mid]target){lmid1;}else{rmid;}}returnl;}}公式解释最关键对某个人到达时间time开放花数 已经开放的花数量 - 已经凋谢的花数量已经开放 花开时间 ≤ time已经凋谢 花谢时间 timeend 当天仍开放复杂度排序O(n log n)每个人二分O(m log n)总体O(n log n m log n)空间O(n)这是最优解法能轻松通过题目最大数据量。总结拆分花期为开始数组与结束数组并排序对每个人到达时间用二分计算开花数 - 凋谢数时间复杂度最优、代码简洁、面试高频标准答案需要我给你讲差分法版本更直观的区间计数思路吗