算法题：cnt[logs[j].y]--， j++; // 这行代码是什么意思？

Question

一个算法题：
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。
其中每一行的格式是：
ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式：
第一行包含三个整数 N,D,K。
以下 N 行每行一条日志，包含两个整数 ts 和 id。
输出格式：
按从小到大的顺序输出热帖 id。
每个 id 占一行。
数据范围：
1≤K≤N≤10E5,
0≤ts,id≤10E5,
1≤D≤10000

输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例：表示id为1的帖子点赞数量最多，为3个。
1
3

代码：

const int N = 1e5 + 10;
typedef pair<int, int> PII;
#define x first
#define y second
PII logs[N];
bool st[N];
int cnt[N];

int main()
{
    int n, d, k;
    cin >> n >> d >> k;
    for (int i = 0; i < n; i++)
        cin >> logs[i].x >> logs[i].y;

    sort(logs, logs + n);

    for (int i = 0, j = 0; i < n; i++)
    {
        cnt[logs[i].y]++;
        while (logs[i].x - logs[j].x >= d)
           cnt[logs[j].y]--， j++; // 这行代码是什么意思？
        if (cnt[logs[i].y] >= k)
            st[logs[i].y] = true;
    }

    for (int i = 0; i < N; i++)
        if (st[i])
            cout << i << endl;
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

这行代码 cnt[logs[j].y]--, j++; 在算法中的作用是维护一个滑动窗口，以检测每个帖子在特定时间段内收到的点赞数是否达到热帖的标准。下面是详细的解释：

在这段代码中，我们首先对日志进行排序，按照时间戳 logs[i].x 的顺序排列。然后，我们遍历这些日志，并对每个帖子的点赞数进行计数（cnt[logs[i].y]++）。在这个过程中，我们需要维护一个滑动窗口来检查每个帖子在长度为 d 的时间段内的点赞数是否达到 k 个。滑动窗口是通过递增 j 来实现的，表示我们正在向前移动窗口的起始点。

当 logs[i].x - logs[j].x >= d 成立时，意味着当前时间 logs[i].x 与窗口的起始时间 logs[j].x 之间的间隔已经大于或等于 d，也就是说我们已经离开了一个完整的长度为 d 的时间段。这时我们需要检查该时间段内是否有足够的点赞数。为了实现这一点，我们需要将计数减去先前在这个窗口内未被考虑的点，也就是 cnt[logs[j].y]--。然后递增 j 来移动窗口的起始点。这个过程会一直持续直到我们遍历完所有的日志或者窗口内的点赞数达到热帖的标准。

总结一下，这行代码的作用是更新滑动窗口的起始点，同时确保每个帖子在长度为 d 的时间段内的点赞数被正确计算。通过这种方式，我们可以有效地找出所有成为热帖的帖子编号。