首页deque双头队列实现单调队列

deque双头队列实现单调队列

时间: 2025-02-04 09:43:26 浏览: 55

### 使用 `deque` 实现单调队列为了实现一个高效的滑动窗口最大值算法，可以利用 Python 中的双端队列 (`collections.deque`) 来构建单调队列。这种数据结构允许在一端或两端快速插入和删除元素。 #### 单调队列的特点 - 只保存有可能成为窗口里最大值的那些元素下标。 - 队列中的元素按照对应的数值大小降序排列，即保持队首始终是当前窗口的最大值[^5]。 #### 关键操作解析 - **入队**: 当新元素加入时，会把队列中所有小于等于该元素的值移除，因为这些较小的值不可能再有机会成为未来的最大值。 - **出队**: 如果即将离开窗口范围的第一个元素正好是最前面的那个大数，则将其弹出；否则不做任何处理。 - **获取最值**: 由于维护的是递减序列，所以每次查询最值只需要访问队首即可获得结果。下面是具体的代码示例： ```python from collections import deque def maxSlidingWindow(nums, k): if not nums or k == 0: return [] result = [] window = deque() # 存储索引 for i in range(len(nums)): # 移除不在窗口内的元素 if window and window[0] <= i - k: window.popleft() # 维护单调递减性质 while window and nums[i] >= nums[window[-1]]: window.pop() window.append(i) # 添加到结果集中 (当遍历到了至少k个元素之后) if i >= k - 1: result.append(nums[window[0]]) return result ``` 此函数接收两个参数：一个是待处理的一维列表 `nums` ，另一个是指定窗口宽度的正整数 `k` 。它返回一个新的列表，其中包含了每个连续子数组（长度为 `k`）里的最大值。

阅读全文