题目重点：对已排序请求时间戳同时检查 3、20、60 次阈值；被丢弃请求仍占后续配额，是本题关键约束。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练窗口采用 (t−W,t]，阈值分别为 W=1、10、60 秒，容许数量分别 3、20、60；时间戳可以是整数或浮点秒。
- 若一个请求同时违反多档，只计一次 dropped；即使丢弃，它仍保留在原始时间戳序列中参加之后的窗口判断。
解题路线
- 对第 i 个请求，只需看向前第 limit 个到达时间：若 i≥limit 且 t[i]−t[i−limit]<W，当前窗口内至少有 limit+1 个请求，违反该档。
- 分别检查 i−3、i−20、i−60；三者按 OR 合并，只增加一次丢弃计数。原始数组不删丢弃项。
- 不变量是 t 已排序，因此 t[i−limit] 是当前请求往前第 limit 个到达；若该时间仍在窗口内，窗口请求数必超 limit，反之最多 limit。
- 若输入不是已排序数组而是在线流，可按三档队列移除过期时间；因丢弃仍计数，每次到达都必须入所有窗口。
手动走一遍
同一秒到达 4 个请求，前三个不过每秒阈值，第 4 个丢弃；第 5 个即使前一个已丢弃，仍和之前 4 个同处窗口，也丢弃。到达恰好 t+1 秒时，t 的请求按开边界不再计入 1 秒窗口。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count dropped requests while all arrivals count toward future quotas."""
def dropped_requests(timestamps: list[int]) -> int:
if any(timestamps[i] < timestamps[i - 1] for i in range(1, len(timestamps))):
raise ValueError("timestamps must be sorted")
dropped = 0
for index, current in enumerate(timestamps):
over_one = index >= 3 and current - timestamps[index - 3] < 1
over_ten = index >= 20 and current - timestamps[index - 20] < 10
over_sixty = index >= 60 and current - timestamps[index - 60] < 60
if over_one or over_ten or over_sixty:
dropped += 1
return dropped
复杂度
已排序数组长度 N：每项最多三次索引比较，O(N) 时间、O(1) 额外空间；输入时间戳本身 O(N)。在线队列版存储最近 60 秒全部请求，空间随窗口请求率增长。
易错点与追问
容易失分的边界
- 丢弃后从窗口历史移除该请求，使后续放行过多。
- 同一请求违反两档时计两次 dropped。
- 把边界 t−W 也算在开区间内，却未解释窗口定义。
继续深挖
- 如果丢弃请求不再占额度，三档队列的更新顺序怎样改变？
- 多实例共享限流键时如何实现一致性，并比较严格限流与高吞吐近似？
