首页单调队列和deque

单调队列和deque

时间: 2025-02-01 07:06:04 浏览: 35

### 单调队列概念单调队列是一种特殊的队列，在这种队列中元素按照某种顺序排列，通常是非递增或非递减的。这意味着当新元素加入时，会移除那些违反当前设定顺序的所有旧元素。这样的性质使得单调队列非常适合解决滑动窗口最大值/最小值等问题。 #### 实现细节由于单调队列需要支持快速地从前端和后端添加或删除元素，因此使用 `deque`（双端队列）来实现是非常合适的。Deque 提供了 O(1) 时间复杂度的操作用于在两端插入和弹出元素[^3]。下面是一个基于 Python 的简单例子，展示了如何利用内置模块 collections.deque 来创建一个维护非严格降序序列的单调队列： ```python from collections import deque class MonotonicQueue: def __init__(self): self.q = deque() def push(self, n): while self.q and self.q[-1] < n: self.q.pop() self.q.append(n) def max(self): return self.q[0] def pop(self, n): if n == self.q[0]: self.q.popleft() ``` 在这个类定义里: - 方法 `push()` 接受一个新的整数值并将其压入到 Deque 中；在此之前先清除掉所有小于该值的现有成员以维持内部有序状态。 - 函数 `max()` 返回当前队首的最大项——即整个队列中的最高值。 - 当调用 `pop()` 并传入要移除的具体数值时，如果这个数正好位于队头，则实际执行一次左端移除动作；否则不做任何改变。通过这种方式构建起来的数据结构可以高效处理涉及连续子区间最值查询的任务，并且每次更新都能保证线性时间内的最优解计算效率[^4]。

阅读全文