双端队列,求解《933. 最近的请求次数》
collections.deque()
:
append()
队头 appendleft()
pop()
对头 popleft()
ArrayDeque
offerLast()
队头 offerFirst()
pollLast()
队头 pollFirst()
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类:
RecentCounter() 初始化计数器,请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求,其中 t 表示以毫秒为单位的某个时间,并返回过去 3000 毫秒内发生的所有请求数(包括新请求)。确切地说,返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
var RecentCounter = function() {
this.q = []
};
RecentCounter.prototype.ping = function(t) {
this.q.push(t)
while (this.q[0] < t - 3000) this.q.shift()
return this.q.length
};
class RecentCounter {
q: number[] = []
constructor() {
}
ping(t: number): number {
this.q.push(t)
while (this.q[0] < t - 3000) this.q.shift()
return this.q.length
}
}
type RecentCounter struct {
q []int
}
func Constructor() RecentCounter {
return RecentCounter{q: []int{}}
}
func (this *RecentCounter) Ping(t int) int {
this.q = append(this.q, t)
for this.q[0] < t - 3000 {
this.q = this.q[1:]
}
return len(this.q)
}
class RecentCounter {
private $q;
function __construct() {
$this->q = [];
}
function ping($t) {
$this->q []= $t;
while ($this->q[0] < $t - 3000) array_shift($this->q);
return count($this->q);
}
}
class RecentCounter(object):
def __init__(self):
self.q = deque()
def ping(self, t):
self.q.append(t)
while self.q[0] < t - 3000: self.q.popleft()
return len(self.q)
class RecentCounter {
private Deque<Integer> q;
public RecentCounter() {
q = new ArrayDeque<>();
}
public int ping(int t) {
q.offerLast(t);
while (q.getFirst() < t - 3000) q.pollFirst();
return q.size();
}
}
class RecentCounter {
private Deque<Integer> q;
public RecentCounter() {
q = new ArrayDeque<>();
}
public int ping(int t) {
q.offer(t);
while (q.peek() < t - 3000) q.poll();
return q.size();
}
}