单调双端队列
2020-03-07 本文已影响0人
madao756
0X00 模板题目
维护一个单调递减(不是严格的是可以等的)的双端队列,双端队列的第一个值是当前队列的最大值
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) 的时间拿到 最大最小值可以使用 「单调双端队列」
