题目描述
给你一个整数 n ，表示服务器的总数目，再给你一个下标从 0 开始的 二维 整数数组 logs ，其中 logs[i] = [server_id, time] 表示 id 为 server_id 的服务器在 time 时收到了一个请求。
同时给你一个整数 x 和一个下标从 0 开始的整数数组 queries 。
请你返回一个长度等于 queries.length 的数组 arr ，其中 arr[i] 表示在时间区间 [queries[i] - x, queries[i]] 内没有收到请求的服务器数目。
注意时间区间是个闭区间。
示例 1：
输入：n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
输出：[1,2]
解释：
对于 queries[0]：id 为 1 和 2 的服务器在区间 [5, 10] 内收到了请求，所以只有服务器 3 没有收到请求。
对于 queries[1]：id 为 2 的服务器在区间 [6,11] 内收到了请求，所以 id 为 1 和 3 的服务器在这个时间段内没有收到请求。
示例 2：
输入：n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
输出：[0,1]
解释：
对于 queries[0]：区间 [1, 3] 内所有服务器都收到了请求。
对于 queries[1]：只有 id 为 3 的服务器在区间 [2,4] 内没有收到请求。
提示：
-
1 <= n <= 10^5 -
1 <= logs.length <= 10^5 -
1 <= queries.length <= 10^5 -
logs[i].length == 2 -
1 <= logs[i][0] <= n -
1 <= logs[i][1] <= 10^6 -
1 <= x <= 10^5 -
x < queries[i] <= 10^6
思路
一开始误以为只有 logs 里面访问过的服务器才生效，其实没列出来的也算数。题目说 n 个服务器，然后给出一些访问列表。
先说下，我第一次拿到手的思路：
- 先建立一个 map，key 为时间点，值为在这个时间点访问了哪些 server。
- 遍历 queries，用两次二分确定当前区间覆盖哪些时间点
- 统计这些时间点访问过的 servers
- 用 n 减去访问过的 servers 数量记为当前 query 的结果
但这样做超时了。然后看了提示说用双指针，滑动窗口？想了半天没想到怎么滑。看完题解：滑动窗口还能这么用？
具体做法是，先将 logs 按时间升序排列，问题转化为定长（x + 1）的滑动窗口问题。因为要按照时间先后与顺序滑动，所以 queries 也要按时间排序。但答案和 queries 的顺序强相关，所以不能直接排序，那就排它的索引。从上一次询问，到这一次询问 q 的过程中，
- 把 的新增请求进入窗口（右边界）
- 把 的请求离开窗口（左边界）
同时维护每个服务器收到了多少个请求 cnt，以及没有收到请求的服务器数目 not_received（初值为 n）：
- 若服务器 i 收到的请求进入窗口，则把
cnt[i]加一，如果加一前等于 0，那么把 not_received 减少一 - 若服务器 i 收到的请求离开窗口，则把
cnt[i]减一，如果减一后等于 0，那么把 not_received 增加一
vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
// logs按时间点升序排列
sort(logs.begin(), logs.end(), [](const vector<int>& a, const vector<int>&b){
return a[1] < b[1];
});
vector<int> idx(queries.size());
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b){ // 排queries的索引
return queries[a] < queries[b];
});
vector<int> cnt(n + 1, 0); // 窗口内每个服务器收到的请求次数，从用例看出server编号从1开始
int not_received = n; // 记录未收到请求的服务器数目
int left = 0, right = 0;
for (int qid : idx) {
int& q = queries[qid];
while (right < logs.size() && logs[right][1] <= q) { // 滑动右边界
int server = logs[right][0];
if (cnt[server]++ == 0) { // server第一次被访问，未被访问的server就减少1
--not_received;
}
++right;
}
while (left < logs.size() && logs[left][1] < q - x) { // 滑动左边界
int server = logs[left][0];
if (--cnt[server] == 0) { // server被访问次数降到0，未被访问的server就加1
++not_received;
}
++left;
}
q = not_received; // 原地修改queries，因为后面用不到了
}
return queries;
}这个题精妙之处在于它的滑窗目标，在哪个数组上面滑不是很明显。它相当于是每次固定一个窗口，在 logs 数组中定界。下一次 query 又换一个窗口，然后我们还得在 logs 数组中滑动至目标窗口。因为滑窗你得一步一步滑，一步一步处理和维护信息，才能边滑边获得你想要的信息。如果直接跳，那就无法处理全部的信息，最后也得不到正确答案。就像这题，先按时间维度排序，把两个数组都变成单向移动的，这样才能套用滑窗。试想一下，如果 queries 不按时间先后排序，有时先问你后面的，有时再问你前面的。这样你滑窗的过程中还得回头处理以前窗口的信息，就复杂了。