题目内容

请实现一个网关 令牌桶限流器。桶容量为 capacity，每经过 $1$ 个整秒补充 rate 个令牌，令牌数不超过容量。初始时刻视为 $0$，此时桶是满的。

在时刻 $t$ 处理请求时：若 $t$ 不早于上次处理时刻 $last$，先按整秒补令牌

再决定是否消耗；若 $t < last$（时间回拨），allow / request 返回 false 且不改状态，tokens 仍返回当前库存、不回拨。

• request 必须一次性凑齐 $n$ 个令牌，否则一个都不扣
• $n\le 0$ 视为非法，返回 false，不补令牌、不改状态
• 即使 $n$ 大于容量（永远放行不了），只要 $t\ge last$ 仍先补令牌

需要实现的接口

• TokenBucket(int capacity, int rate)：容量与每秒补充量。保证 $capacity\ge 1$，$rate\ge 1$
• allow(int t)：时刻 $t$ 请求 $1$ 个令牌，成功 true
• request(int t, int n)：时刻 $t$ 一次请求 $n$ 个令牌，成功 true
• tokens(int t)：补到时刻 $t$（若 $t\ge last$）后的当前令牌数，不消耗
• lastTime()：上次成功补令牌的时刻（构造后为 $0$；时间回拨的失败调用不更新）

输入描述

每行一次函数调用。首行 TokenBucket(capacity, rate)。累计调用不超过 $3000$ 次。

• $1 \le \textit{capacity} \le 1000$
• $1 \le \textit{rate} \le 100$
• $0 \le t \le 10^9$
• $n$ 为整数，可能非正或大于容量

补令牌时 $(t-last)\cdot rate$ 可能超过 $32$ 位，实现时用 $64$ 位再与容量取最小。

输出描述

• 构造返回 null
• allow / request 返回 true 或 false
• tokens / lastTime 返回整数

样例1

输入：

TokenBucket(2, 1)
tokens(0)
allow(0)
allow(0)
allow(0)
tokens(0)
allow(1)
tokens(3)
lastTime()

输出：

null
2
true
true
false
0
true
2
3

说明：时刻 $0$ 桶满为 $2$，连续两次 allow 耗尽。同一时刻第三次失败。时刻 $1$ 先补 $1$ 再消耗。再查时刻 $3$ 又补 $2$ 秒，封顶仍为 $2$。若先消耗再补令牌，时刻 $1$ 的 allow 会失败。

样例2

输入：

TokenBucket(2, 1)
request(0, 3)
tokens(0)
request(0, 2)
tokens(0)
request(0, 0)

输出：

null
false
2
true
0
false

说明：$3>2$，满桶也放行不了，库存不变。随后一次取走 $2$ 个。$n=0$ 非法。

样例3

输入：

TokenBucket(1, 1)
allow(5)
allow(3)
tokens(3)
tokens(6)
lastTime()

输出：

null
true
false
0
1
6

说明：时刻 $5$ 放行后库存为 $0$。时刻 $3$ 回拨，allow 失败且不改状态；tokens(3) 仍为 $0$。时刻 $6$ 才补 $1$ 个。