题目描述

巧用双指针，维护时间区间

样例

import java.util.*;

/*
   暴力法：
   第一层循环是 时间0到最大时间(最远点赞时间)
   第二层循环是 所有的id判断它的时刻是否属于要求的长度的时间区间
   是的话就统计它的次数 +1
   然后判断一下它的次数是否已经>k 是的话将布尔数组它的位置 置为true
   然后再每次判断新的时间区间时 要将cnt初始化为全0
   for(int time = 0;time <= maxt; time++)
    {
    Arrays.fill(cnt,0)
    for(int i = 1;i<=n;i++)
    {
        int t = blog[i].x;
        int id = blog[i].y;
        if( t >= time && t <time+d)
            cnt[id]++;
        if(cnt[id] >= k)
            hot[id] = true;
    }
    }
    for(int i = 0;i<=N;i++)
    if(st[i]) System.out.println(i);

   双指针算法：
   a是根据升序时间区间升序排列的记录数组(所有记录都有，样例中100 3 100 3，也是存两次)
   双指针是在a内访问，而while循环做的工作就是将这个区间进行归位
   若i前移过程超出了时间区间d, j就向前移 找到符合要求的下一个区间位置,并且要退回之前的cnt(也就是--操作)
   因为j已经追随i到了下一个区间了，所以这个j位置对应的id的赞数就不符合D的时间区间要求了，要执行cnt[logs[j].y]–-
   也就是在while循环里 先执行cnt[logs[j].y]--，再进行j前移，如果调换顺序，则进行--操作的j位置就不对了。
*/

public class Main {
    static class Pair {
        int x, y;
        public Pair(int x, int y) {
            this.x = x;//x是时间
            this.y = y;//y是编号
        }
    }

    static int N = 100010;
    static int[] cnt = new int[N];//用来记录每个编号的点赞数
    static boolean[] st = new boolean[N];//用来记录是否是热帖

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int d = scanner.nextInt();
        int k = scanner.nextInt();

        Pair[] logs = new Pair[n];
        for (int i = 0; i < n; i++) {
            logs[i] = new Pair(scanner.nextInt(), scanner.nextInt());
        }


        //所有记录按时间排序
        Arrays.sort(logs, Comparator.comparingInt(a -> a.x));
        //Arrays.sort(logs, (p1, p2) -> p1.x - p2.x);正序可以简写成上面
        //Arrays.sort(logs, (p1, p2) -> p2.x - p1.x);逆序没有简写

        for (int i = 0, j = 0; i < n; i++) {
            int id = logs[i].y;//得到当前的编号
            cnt[id]++;//当前的编号点赞数加1

            while (logs[i].x - logs[j].x >= d) {
                cnt[logs[j].y]--;
                j++;
            }

            if (cnt[id] >= k) st[id] = true;
        }

        for (int i = 0; i < N; i++) {
            if (st[i]) {
                System.out.println(i);
            }
        }
    }
}