题目描述
给你一个整数 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]]
内没有收到请求的服务器数目。
注意时间区间是个闭区间。
样例
输入: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 的服务器在这个时间段内没有收到请求。
输入: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
算法
(排序,滑动窗口) $O(n + k \log k + q \log q)$
- 将询问从小到大排序,将请求按照时间也从小到大排序。
- 直接在排序后的请求数组上定义滑动窗口,按顺序遍历询问。对于每个询问的时间 $L$,移动滑动窗口的右侧 $t$,直到 $logs[t]$ 的时间大于 $L$,然后移动滑动窗口的左侧 $h$,直到 $logs[h]$ 的时间不小于 $L - x$。窗口 $[h, t]$ 就是这个询问对应的请求区间。
- 在窗口下标移动过程中动态维护当前窗口中没有接收到请求的服务器的个数,用这个个数更新每个询问的答案。
时间复杂度
- 排序的时间复杂度为 $O(k \log k + q \log q)$,其中 $k$ 为总的请求次数。
- 排序后,需要 $O(n + k + q)$ 的时间复杂度遍历滑动窗口和所有询问。
- 故总时间复杂度为 $O(n + k \log k + q \log q)$。
空间复杂度
- 需要 $O(n + q + \log k)$ 的额外空间存储答案,滑动窗口的访问记录以及排序的系统栈。
C++ 代码
class Solution {
public:
vector<int> countServers(int n, vector<vector<int>>& logs, int x,
vector<int>& queries
) {
const int q = queries.size();
vector<int> qid(q);
iota(qid.begin(), qid.end(), 0);
sort(qid.begin(), qid.end(), [&](int x, int y) {
return queries[x] < queries[y];
});
sort(logs.begin(), logs.end(), [](const vector<int> &x, const vector<int> &y) {
return x[1] < y[1];
});
vector<int> seen(n, 0);
int cnt = n;
vector<int> ans(q);
for (int i = 0, h = 0, t = 0; i < q; i++) {
while (t < logs.size() && logs[t][1] <= queries[qid[i]]) {
++seen[logs[t][0] - 1];
if (seen[logs[t][0] - 1] == 1)
--cnt;
++t;
}
while (h < t && logs[h][1] < queries[qid[i]] - x) {
--seen[logs[h][0] - 1];
if (seen[logs[h][0] - 1] == 0)
++cnt;
++h;
}
ans[qid[i]] = cnt;
}
return ans;
}
};