3851. 不违反限制的最大请求数 🔒

题目描述

给定一个二维整数数组 requests，其中 requests[i] = [user_i, time_i] 表示 user_i 在 time_i 进行了一次请求。

同时给定两个整数 k 和 window。

如果存在一个整数 t，使得某个用户在闭区间 [t, t + window] 内的请求次数严格大于 k，则用户违反了限制。

可以丢弃任意数量的请求。

返回一个整数，表示没有用户违反限制的可保留的最大请求数。

示例 1：

输入：requests = [[1,1],[2,1],[1,7],[2,8]], k = 1, window = 4

输出：4

解释：

对于用户 1，请求时间是 [1, 7]。它们的差是 6，这大于 window = 4。
对于用户 2，请求时间是 [1, 8]。它们的差是 7，这同样大于 window = 4。
任何 window 长度的闭区间内，用户发出的请求数不超过 k = 1，因此所有 4 个请求都可以保留。

示例 2：

输入：requests = [[1,2],[1,5],[1,2],[1,6]], k = 2, window = 5

输出：2

解释：

对于用户 1，请求时间是 [2, 2, 5, 6]。长度为 window = 5 的闭区间 [2, 7] 包含所有 4 个请求。
由于 4 严格大于 k = 2，必须至少移除 2 个请求。
在移除任意 2 个请求后，长度为 window 的每个闭区间包含最多 k = 2 个请求。
因此，最多可以保留的请求数是 2。

示例 3：

输入：requests = [[1,1],[2,5],[1,2],[3,9]], k = 1, window = 1

输出：3

解释：

对于用户 1，请求时间是 [1, 2]。差值为 1，这等于 window = 1。
闭区间 [1, 2] 同时包含这两个请求，所以计数为 2，超过了 k = 1。必须移除一个请求。
用户 2 和用户 3 各自只有一条请求，且均未超出限制。因此，最多可以保留的请求数是 3。

提示：

1 <= requests.length <= 10⁵
requests[i] = [user_i, time_i]
1 <= k <= requests.length
1 <= user_i, time_i, window <= 10⁵

解法

方法一：滑动窗口 + 双端队列

我们可以将请求按照用户进行分组，放在哈希表 \(g\) 中，其中 \(g[u]\) 是用户 \(u\) 的请求时间列表。对于每个用户，我们需要从请求时间列表中删除一些请求，使得在任意长度为 \(window\) 的区间内，剩余的请求数不超过 \(k\)。

我们初始化答案 \(\textit{ans}\) 为请求的总数。

对于用户 \(u\) 的请求时间列表 \(g[u]\)，我们首先对其进行排序。然后，我们使用一个双端队列 \(kept\) 来维护当前保留的请求时间。我们遍历请求时间列表中的每个请求时间 \(t\)，对于每个请求时间，我们需要将 \(kept\) 中所有与 \(t\) 的差值大于 \(window\) 的请求时间删除掉。然后，如果 \(kept\) 中剩余的请求数小于 \(k\)，我们就将 \(t\) 添加到 \(kept\) 中，否则我们需要删除 \(t\)，并将答案减 1。

最后返回答案 \(\textit{ans}\)。

时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(n)\)，其中 \(n\) 是请求的数量。每个请求被访问一次，排序需要 \(O(n \log n)\) 的时间，哈希表和双端队列的操作需要 \(O(n)\) 的时间。

Python3JavaC++GoTypeScriptRust

class Solution:
    def maxRequests(self, requests: list[list[int]], k: int, window: int) -> int:
        g = defaultdict(list)
        for u, t in requests:
            g[u].append(t)
        ans = len(requests)
        for ts in g.values():
            ts.sort()
            kept = deque()
            for t in ts:
                while kept and t - kept[0] > window:
                    kept.popleft()
                if len(kept) < k:
                    kept.append(t)
                else:
                    ans -= 1
        return ans

class Solution {
    public int maxRequests(int[][] requests, int k, int window) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int[] r : requests) {
            int u = r[0], t = r[1];
            g.computeIfAbsent(u, x -> new ArrayList<>()).add(t);
        }

        int ans = requests.length;
        ArrayDeque<Integer> kept = new ArrayDeque<>();

        for (List<Integer> ts : g.values()) {
            Collections.sort(ts);
            kept.clear();
            for (int t : ts) {
                while (!kept.isEmpty() && t - kept.peekFirst() > window) {
                    kept.pollFirst();
                }
                if (kept.size() < k) {
                    kept.addLast(t);
                } else {
                    --ans;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxRequests(vector<vector<int>>& requests, int k, int window) {
        unordered_map<int, vector<int>> g;
        for (auto& r : requests) {
            g[r[0]].push_back(r[1]);
        }

        int ans = requests.size();
        for (auto& [_, ts] : g) {
            sort(ts.begin(), ts.end());
            queue<int> kept;
            int deletions = 0;

            for (int t : ts) {
                while (!kept.empty() && t - kept.front() > window) {
                    kept.pop();
                }
                if (kept.size() < k) {
                    kept.push(t);
                } else {
                    ans--;
                }
            }
        }
        return ans;
    }
};

func maxRequests(requests [][]int, k int, window int) int {
    g := make(map[int][]int)
    for _, r := range requests {
        u, t := r[0], r[1]
        g[u] = append(g[u], t)
    }
    ans := len(requests)
    for _, ts := range g {
        sort.Ints(ts)
        kept := make([]int, 0)
        for _, t := range ts {
            for len(kept) > 0 && t-kept[0] > window {
                kept = kept[1:]
            }
            if len(kept) < k {
                kept = append(kept, t)
            } else {
                ans--
            }
        }
    }
    return ans
}

function maxRequests(requests: number[][], k: number, window: number): number {
    const g = new Map<number, number[]>();
    for (const [u, t] of requests) {
        if (!g.has(u)) g.set(u, []);
        g.get(u)!.push(t);
    }
    let ans = requests.length;
    for (const ts of g.values()) {
        ts.sort((a, b) => a - b);
        const kept: number[] = [];
        let head = 0;
        for (const t of ts) {
            while (head < kept.length && t - kept[head] > window) {
                head++;
            }
            if (kept.length - head < k) {
                kept.push(t);
            } else {
                --ans;
            }
        }
    }
    return ans;
}

use std::collections::{HashMap, VecDeque};

impl Solution {
    pub fn max_requests(requests: Vec<Vec<i32>>, k: i32, window: i32) -> i32 {
        let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
        for r in &requests {
            let u: i32 = r[0];
            let t: i32 = r[1];
            g.entry(u).or_insert_with(Vec::new).push(t);
        }

        let mut ans: i32 = requests.len() as i32;
        let mut kept: VecDeque<i32> = VecDeque::new();

        for ts in g.values_mut() {
            ts.sort();
            kept.clear();

            for &t in ts.iter() {
                while let Some(&front) = kept.front() {
                    if t - front > window {
                        kept.pop_front();
                    } else {
                        break;
                    }
                }

                if kept.len() < k as usize {
                    kept.push_back(t);
                } else {
                    ans -= 1;
                }
            }
        }

        ans
    }
}

3851. 不违反限制的最大请求数 🔒

题目描述

解法

方法一：滑动窗口 + 双端队列

评论