问题描述：
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
来源：力扣（LeetCode）
对于这道题目，难点在如何在求解max_value的时候保持时间复杂度都是O(1)
对于max_value函数，通常会这样思考：每次入队操作时都更新最大值，但当这个最大值出栈之后，我们就无法判断队列中下一个最大值是什么啦
那怎么解决这个问题呢？
我参考了一下其他人的思想 真的yyds
首先设置两个队列，一个是queue.Queue
另一个是queue.deque(专门存放最大值和第二大值的队列)
我们可以在每次入队的时候记录这个队列中除了最大值之外第二大的数呀
那怎么实现呢？
那就so easy了，直接在入队的时候判断队列中的值，如果小于这个即将输入的值，那么我们就把这些在队列中（小）的数依次pop出队列，然后再将这个入队的数append进如deque
那出队的时候怎么做呢？
判断queue.Queue.get(),即出队的数和queue.deque[0]比较，如果不相等，则只是queue.Queue出队，否则，则两个队列一起出队。因为queue.deque[0]每次存储的值都是最大值的位置。
那为什么这样做了之后算max_value的值时间复杂度就变成了O(1)了呢？
每次判断max_value的时候只用让queue.deque[0]出队即可，无需循环。
最后，上官方代码：
#python
import queue
class MaxQueue:
"""1队列+1双端队列"""
def __init__(self):
self.queue = queue.Queue()
self.deque = queue.deque()
def max_value(self) -> int:
if self.deque:
return self.deque[0]
else:
return -1
# return self.deque[0] if self.deque else -1 或者这样写
def push_back(self, value: int) -> None:
while self.deque and self.deque[-1] < value:
self.deque.pop()
self.deque.append(value)
self.queue.put(value)
def pop_front(self) -> int:
if not self.deque: return -1
ans = self.queue.get()
if ans == self.deque[0]:
self.deque.popleft()
return ans
#java
public MaxQueue() {
q = new LinkedList<Integer>();
d = new LinkedList<Integer>();
}
public int max_value() {
if (d.isEmpty()) {
return -1;
}
return d.peekFirst();
}
public void push_back(int value) {
while (!d.isEmpty() && d.peekLast() < value) {
d.pollLast();
}
d.offerLast(value);
q.offer(value);
}
public int pop_front() {
if (q.isEmpty()) {
return -1;
}
int ans = q.poll();
if (ans == d.peekFirst()) {
d.pollFirst();
}
return ans;
}
}
网友评论