Acwing 1238.日志统计 双指针

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N� 行。

其中每一行的格式是：

ts id  

表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式

第一行包含三个整数 N,D,K

以下 N�行每行一条日志，包含两个整数 ts和 id。

输出格式

按从小到大的顺序输出热帖 id

每个 id 占一行。

数据范围

1≤K≤N≤1051≤105,
0≤ts,id≤1050≤,≤105,
1≤D≤100001≤≤10000

输入样例：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例：

1
3

思路：

因为统计一定时间内是否有效，因此我们首先按照时间顺序将输入序列排序。我们使用数组id记录每个id的帖子被点赞的次数，当次数大于k时，我们将相对应的t数组下标元素改变为true,说明该id的帖子达到要求。

但是我们在考虑次数时还要考虑时间的连续性。这也是我们使用双指针的原因，维护一个区间使得该区间内的时间维持在d时间中。如果超出，我们就需要对超出部分元素的次数减1（这里可能不好理解，这个-1能进行是因为这个区间是从前向后遍历的，并且已经按照时间顺序排序。如果之前有元素超出了并且已经>=k，我们-1后不影响t数组的结果。也就是说只保留局部结果）同时将j++

代码：

package lanqiao;import java.util.*;
public class Main{public static void main(String[] args) {int[] id = new int[100000];boolean[] t = new boolean[100000];Scanner sc = new Scanner(System.in);int n = sc.nextInt();int d = sc.nextInt();int k = sc.nextInt();int[][] arr = new int[n][2];for (int i = 0; i < n; i++) {int i1 = sc.nextInt();int i2 = sc.nextInt();arr[i] = new int[]{i1,i2};}sc.close();Arrays.sort(arr,(a,b) -> (a[0] - b[0]));List<Integer> ans = new ArrayList<>();for (int i = 0, j =0; i < n; i++) {id[arr[i][1]]++;while(arr[i][0] - arr[j][0] >= d){id[arr[j][1]]--;j++;}if(id[arr[i][1]] >= k) t[arr[i][1]] = true;}for (int i = 0; i < t.length; i++) {if(t[i]) System.out.println(i);}}
}