Leetcode 2747. Count Zero Request Servers

[Woodyiiiiiii]

2747. Count Zero Request Servers

2747. Count Zero Request Servers

这道题一开始我就想着用滑动窗口来做，那样我们每次只关注左右指针的变化情况就行了。但问题是，如果在左右指针所指向的时间之内，存在多个server呢？所以代码中体现的是要遍历两个时间点的所有servers，最坏情况下时间复杂度很高。

有没有办法优化？我首先想的是排序，对queries(arr)数组排序，但后来以为没什么关联就放弃了。但似乎只有排序这条路可以走了。对arr数组(询问数组)排序后，接着对logs数组排序，然后按顺序遍历。

不理解的点在于内外都是n，不会超时吗？其实，每个时间点入队和出队只有一次，而且内外变量是同一个，范围也是同一个，并不是严格意义上的每个外层n都有内层n。

一道很好的排序+滑动窗口的题目，难点在于考验时间复杂度的计算以及排序。

class Solution {
    public int[] countServers(int n, int[][] logs, int x, int[] queries) {
        int[][] sortQueries = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            sortQueries[i][0] = queries[i];
            sortQueries[i][1] = i;
        }
        Arrays.sort(logs, Comparator.comparingInt(a -> a[1]));
        Arrays.sort(sortQueries, Comparator.comparingInt(a -> a[0]));
        Map<Integer, Integer> cntMap = new HashMap<>();
        int[] ans = new int[queries.length];
        int l = 0, r = 0;
        for (int[] query : sortQueries) {
            int right = query[0], left = query[0] - x;
            while (r < logs.length && logs[r][1] <= right) {
                int server = logs[r][0];
                cntMap.put(server, cntMap.getOrDefault(server, 0) + 1);
                r++;
            }
            while (l < logs.length && logs[l][1] < left) {
                int server = logs[l][0];
                cntMap.put(server, cntMap.getOrDefault(server, 0) - 1);
                if (cntMap.get(server) == 0) {
                    cntMap.remove(server);
                }
                l++;
            }
            ans[query[1]] = n - cntMap.size();
        }
        return ans;
    }
}