跳转至

3851. Maximum Requests Without Violating the Limit 🔒

题目描述

You are given a 2D integer array requests, where requests[i] = [useri, timei] indicates that useri made a request at timei.

You are also given two integers k and window.

A user violates the limit if there exists an integer t such that the user makes strictly more than k requests in the inclusive interval [t, t + window].

You may drop any number of requests.

Return an integer denoting the maximum​​​​​​​ number of requests that can remain such that no user violates the limit.

 

Example 1:

Input: requests = [[1,1],[2,1],[1,7],[2,8]], k = 1, window = 4

Output: 4

Explanation:​​​​​​​

  • For user 1, the request times are [1, 7]. The difference between them is 6, which is greater than window = 4.
  • For user 2, the request times are [1, 8]. The difference is 7, which is also greater than window = 4.
  • No user makes more than k = 1 request within any inclusive interval of length window. Therefore, all 4 requests can remain.

Example 2:

Input: requests = [[1,2],[1,5],[1,2],[1,6]], k = 2, window = 5

Output: 2

Explanation:​​​​​​​

  • For user 1, the request times are [2, 2, 5, 6]. The inclusive interval [2, 7] of length window = 5 contains all 4 requests.
  • Since 4 is strictly greater than k = 2, at least 2 requests must be removed.
  • After removing any 2 requests, every inclusive interval of length window contains at most k = 2 requests.
  • Therefore, the maximum number of requests that can remain is 2.

Example 3:

Input: requests = [[1,1],[2,5],[1,2],[3,9]], k = 1, window = 1

Output: 3

Explanation:

  • For user 1, the request times are [1, 2]. The difference is 1, which is equal to window = 1.
  • The inclusive interval [1, 2] contains both requests, so the count is 2, which exceeds k = 1. One request must be removed.
  • Users 2 and 3 each have only one request and do not violate the limit. Therefore, the maximum number of requests that can remain is 3.

 

Constraints:

  • 1 <= requests.length <= 105
  • requests[i] = [useri, timei]
  • 1 <= k <= requests.length
  • 1 <= useri, timei, window <= 105

解法

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

我们可以将请求按照用户进行分组，放在哈希表 \(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)\) 的时间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
    }
}

评论