問題描述：
請定義一個隊列并實現(xiàn)函數(shù) max_value 得到隊列里的最大值，要求函數(shù)max_value、push_back 和 pop_front 的均攤時間復(fù)雜度都是O(1)。
若隊列為空，pop_front 和 max_value?需要返回 -1
來源：力扣（LeetCode）
對于這道題目，難點在如何在求解max_value的時候保持時間復(fù)雜度都是O(1)
對于max_value函數(shù)，通常會這樣思考：每次入隊操作時都更新最大值，但當(dāng)這個最大值出棧之后，我們就無法判斷隊列中下一個最大值是什么啦
那怎么解決這個問題呢？
我參考了一下其他人的思想 真的yyds
首先設(shè)置兩個隊列，一個是queue.Queue
另一個是queue.deque(專門存放最大值和第二大值的隊列)
我們可以在每次入隊的時候記錄這個隊列中除了最大值之外第二大的數(shù)呀
那怎么實現(xiàn)呢？
那就so easy了，直接在入隊的時候判斷隊列中的值，如果小于這個即將輸入的值，那么我們就把這些在隊列中（?。┑臄?shù)依次pop出隊列，然后再將這個入隊的數(shù)append進如deque
那出隊的時候怎么做呢？
判斷queue.Queue.get(),即出隊的數(shù)和queue.deque[0]比較，如果不相等，則只是queue.Queue出隊，否則，則兩個隊列一起出隊。因為queue.deque[0]每次存儲的值都是最大值的位置。
那為什么這樣做了之后算max_value的值時間復(fù)雜度就變成了O(1)了呢？
每次判斷max_value的時候只用讓queue.deque[0]出隊即可，無需循環(huán)。
最后，上官方代碼：
#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;
? ? }
}
