Topic describes

Define a queue and implement the max_value function to get the maximum value in the queue, requiring the amortized time complexity of max_value, push_back, and pop_front to be O(1).

If the queue is empty, pop_front and max_value must return -1

Example 1: input: [” MaxQueue “, “push_back push_back”, “max_value”, “pop_front”, “max_value”] [[], [1], [2], [], [], []] output: 2,1,2] [null, null, null,

Example 2: input: [” MaxQueue “, “pop_front”, “max_value”] [[], [], []] output: (null, 1, 1)

Priority queue

  1. Requiring access to be O(1) time, we cannot use traversal. Here we use priority queues
  2. To join the queue, the element is added to the mainQueue; Discard all elements smaller than the current element in the sortQueue
  3. The mainQueue header is unqueued, and the queue header is unqueued. If so, the queue header is unqueued

The sample code

class MaxQueue:
    def __init__(self) :
        self.mainQueue = []
        self.sortQueue = []

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

    def push_back(self, value: int) - >None:
        self.mainQueue.append(value)
        Discard all entries in the sortQueue smaller than val
        while self.sortQueue and value > self.sortQueue[-1]:
            self.sortQueue.pop()
        self.sortQueue.append(value)

    def pop_front(self) - >int:
        if self.mainQueue:
            Check whether the queue head of sortQueue is queued
            first = self.mainQueue.pop(0)
            if first == self.sortQueue[0]:
                self.sortQueue.pop(0)
            return first
        else:
            return -1

Copy the code