单调双端队列

0X00 模板题目

面试题59 - II. 队列的最大值 LCOF

维护一个单调递减(不是严格的是可以等的)的双端队列,双端队列的第一个值是当前队列的最大值

from collections import deque
class MaxQueue:

    def __init__(self):
        self.queue = deque()
        self.helper = deque()

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

    def push_back(self, value: int) -> None:
        # 维护一个单调递减的队列
        while self.helper and self.helper[-1] < value:
            self.helper.pop()
        self.helper.append(value)
        self.queue.appendleft(value)
        
    def pop_front(self) -> int:
        if not self.queue: return -1
        ans = self.queue.pop()
        if ans == self.helper[0]:
            self.helper.popleft()
        return ans

0X01 注意事项

什么时候使用「单调双端队列」

维护一个队列的最大值,最小值,此时为了保证 O(1) 的时间拿到 最大最小值可以使用 「单调双端队列」

0X02 相关题目

• 239. Sliding Window Maximum