2251. 花期内花的数目 (opens new window)

1.差分数组+排序队列

解题思路：典型的差分数组。本题花期在10的9次方量级，因此此处开辟差分数组容易爆内存。

差分数组的本质在于，每经历一个时刻当前差分累加数量都会改变，所以可以采用排序队列的方法。具体来说，将起始时间放入一个递增序列，终止时间放入另一个递增序列。遍历游客看花时刻也按照有序进行。

1. 当前时刻time，并从起止时间分别取出下一个改变时刻time1，time2。
2. 如果当前客人观赏的时间在time和下一个改变时刻之间，那么当前数量即为当前客人所能看到的数目。(注意最终结果需要按照客人的序列返回)
3. 取出下一个最小改变时刻Min(time1,time2)作为当前时刻。并更新当前数量。

其中存在一些细节问题如下：

• 结束时刻为endTime，那么实际上endTime+1时刻花的数量才会减一发生改变。
• 存在多个相同的起始和结束时刻，在判断游客观赏时刻前需要提前出队列。保证当前时刻计算得到的数量是正确的。

class Solution {
	public static int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int[] res=new int[people.length];
        int[][] peopleWithLocation = new int[people.length][2];
        for(int i=0;i<people.length;i++){
            peopleWithLocation[i][0]=i;
            peopleWithLocation[i][1] = people[i];
        }
        Arrays.sort(peopleWithLocation, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        PriorityQueue<Integer> start = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        PriorityQueue<Integer> end = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int i = 0; i < flowers.length; i++) {
            start.offer(flowers[i][0]);
            end.offer(flowers[i][1]);
        }
        int cnt=1;
        int time = start.poll();
        int inx=0;
        while (!start.isEmpty() || !end.isEmpty()) {
            //处理相同时刻
            while(!start.isEmpty()&&start.peek()==time){
                start.poll();
                cnt++;
            }
            while(!end.isEmpty()&&end.peek()+1==time){
                end.poll();
                cnt--;
            }
            int time1 = start.isEmpty() ? Integer.MAX_VALUE : start.peek();
            int time2 = end.isEmpty() ? Integer.MAX_VALUE : end.peek()+1;
            for (int i = inx; i < peopleWithLocation.length; i++) {
                int peopleTime = peopleWithLocation[i][1];
                if(peopleTime>=time&&peopleTime<time1&&peopleTime<time2) res[peopleWithLocation[i][0]]=cnt;
                else if(peopleTime<time) continue;
                else{
                    inx=i;
                    break;
                }
            }
            if(time1<time2){
                time=time1;
                if(!start.isEmpty()) start.poll();
                cnt++;
            } else if (time1 > time2) {
                time = time2;
                if(!end.isEmpty()) end.poll();
                cnt--;
            } else {
                if(!start.isEmpty()) start.poll();
                if(!end.isEmpty()) end.poll();
                time = time1;
            }
        }
        return res;
    }
}