Jianbo Dai's

jz059II.队列的最大值

 
  • Oct 19, 2020

题目链接https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

这题思想和jz059I很相似。这个算法的时间复杂度（插入，删除，求最大值）是O（1），空间复杂度是O（N）。

import queue

class MaxQueue:

    def __init__(self):
        self.master, self.aux = queue.Queue(), queue.deque()

    def max_value(self) -> int:
        return self.aux[0] if self.aux else -1

    def push_back(self, value: int) -> None:
        self.master.put(value)
        while self.aux and value > self.aux[-1]:
            self.aux.pop()
        self.aux.append(value)

    def pop_front(self) -> int:
        if not self.aux:
            return -1
        else:
            ans = self.master.get()
            if ans == self.aux[0]:
                self.aux.popleft()
            return ans
Search