域名请求限流实现疑问：5秒/30秒请求次数校验求解

我有一个程序，每秒接收不同域名的请求（请求是一个大小为n的字符串数组，每个元素对应一个域名），请求的时间对应数组索引i（单位：秒）。规则要求：

• 同一域名5秒内最多允许2次成功请求
• 同一域名30秒内最多允许5次成功请求
  每个请求需返回"success"（通过）或"error"（拒绝）。

示例 #

n = 9, requests = ["xyz", "abc", "xyz", "pqr", "abc", "xyz", "xyz", "abc", "xyz"]

Result = 
["success", "success", "success", "success", "success", "success", "error", "success", "success"]

解释 #

domain xyz occurs at indices = [0,2,5,6,8]
domain abc = [1,4,7]
domain pqr = [3]

索引6的xyz请求，在5秒范围内已有2次成功请求（索引2和5），因此返回error，其余请求均返回success。

约束条件 #

n range is 1 to 10^4
input string contains lowercase English letters.

我的错误代码 #

public static List<String> solve(List<String> requests) {
    List<String> result = new ArrayList<>();
    Map<String, List<Integer>> map = new HashMap<>();

    int n = requests.size();
    for(int i=0; i<n; i++) {
        String s = requests.get(i);
        int time = i;
        
        // remove items older than 30 seconds
        while(!map.getOrDefault(s, new ArrayList<>()).isEmpty() && time - map.get(s).get(0) >= 30) {
            map.get(s).remove(0);
        }
        
        // remove items older than 5 seconds
        while(!map.getOrDefault(s, new ArrayList<>()).isEmpty() && time - map.get(s).get(0) >= 5) {
            map.get(s).remove(0);
        }
        
        //check if we have 2 successful requests for given domain
        if(map.getOrDefault(s, new ArrayList<>()).size() >= 2) {
            map.get(s).remove(0);
            result.add("error");
        } else {
            result.add("success");
            map.computeIfAbsent(s, k-> new ArrayList<>()).add(time);
        }   
    }
    return result;
}

错误原因分析 #

你的代码存在几个核心问题：

1. 清理顺序错误：先清理30秒外的记录，再清理5秒外的记录，这会导致5秒内的有效记录被误删，无法正确统计5秒内的请求次数。
2. 统计逻辑遗漏：完全忽略了30秒内最多5次的限制，同时错误地在拒绝请求时删除旧记录——拒绝的请求不应该计入成功请求统计，也不需要修改历史记录。
3. getOrDefault误用：每次调用map.getOrDefault(s, new ArrayList<>())都会创建新空列表，导致后续操作的对象可能不是map中实际存储的列表，容易触发空指针异常。

正确解决思路 #

1. 为每个域名维护有序的成功请求时间列表：按请求时间递增存储，方便快速判断时间范围。
2. 分步骤处理过期记录与统计：
   • 先清理30秒外的所有成功记录（30秒范围更大，先处理不影响5秒统计）
   • 统计5秒内的成功请求数量：不需要删除5秒外的记录，从列表末尾往前遍历，遇到超过5秒的记录就停止，统计符合条件的数量。
3. 双重条件判断：
   • 先检查30秒内成功请求数是否达5次，是则拒绝。
   • 再检查5秒内成功请求数是否达2次，是则拒绝。
   • 只有两个条件都未超限，才返回success并将当前时间加入列表。

正确代码实现 #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DomainRateLimiter {
    public static List<String> solve(List<String> requests) {
        List<String> result = new ArrayList<>();
        // 存储每个域名的成功请求时间列表，按时间顺序排列
        Map<String, List<Integer>> domainSuccessTimes = new HashMap<>();

        for (int i = 0; i < requests.size(); i++) {
            String domain = requests.get(i);
            int currentTime = i;
            List<Integer> times = domainSuccessTimes.computeIfAbsent(domain, k -> new ArrayList<>());

            // 清理30秒之前的成功请求记录
            while (!times.isEmpty() && currentTime - times.get(0) >= 30) {
                times.remove(0);
            }

            // 检查30秒内是否已经达到5次成功请求
            if (times.size() >= 5) {
                result.add("error");
                continue;
            }

            // 统计5秒内的成功请求数量
            int count5s = 0;
            // 从后往前遍历，因为列表是递增的，遇到超过5秒的就停止
            for (int j = times.size() - 1; j >= 0; j--) {
                if (currentTime - times.get(j) < 5) {
                    count5s++;
                } else {
                    break;
                }
            }

            // 检查5秒内是否已经达到2次成功请求
            if (count5s >= 2) {
                result.add("error");
            } else {
                result.add("success");
                times.add(currentTime);
            }
        }

        return result;
    }
}

代码优化说明 #

• 清理30秒过期记录时，利用列表有序性从头部删除，时间复杂度低。
• 统计5秒内请求数时从末尾往前遍历，避免不必要的遍历操作，提升效率。
• 拒绝请求时不修改成功请求列表，确保统计数据准确。
• 使用computeIfAbsent确保每个域名对应的列表存在，避免空指针异常。

内容的提问来源于stack exchange，提问作者Learner