Python collections.deque：双面娇娃与滑动窗口的华尔兹
大家好！欢迎来到今天的“Python奇技淫巧”讲座，我是你们的老朋友，代码界的郭德纲。今天咱们不聊相声，聊聊Python标准库里一个低调但实力超群的模块：collections。而这个模块里的明星，就是我们今天要重点介绍的deque（发音类似“deck”）。
deque，全称“double-ended queue”，翻译过来就是“双端队列”。 顾名思义，它像一个两头都可以进出的队列。这东西听起来好像平平无奇，但实际上，它在很多场景下都能发挥巨大的作用，尤其是处理滑动窗口这类问题，那叫一个得心应手。
什么是双端队列？
在深入deque的用法之前，咱们先来简单复习一下队列的基本概念。 队列就像排队买票，先进先出（FIFO）。 你只能在队尾（rear）添加元素，只能从队首（front）移除元素。
而deque呢，就厉害了。 它打破了这个规则，允许你从队首和队尾同时进行添加和删除操作。 想象一下，你排队买票，突然发现队伍太长了，可以直接从队尾溜走，或者临时有事，插到队伍最前面（当然，现实中这么做会被打的）。 这就是deque的魔力。
deque的优点
你可能会问，既然Python的list也能实现队列的功能（用append和pop(0)），那为什么还要用deque呢？ 问得好！ 这就是deque的闪光点：效率。
list的劣势：list在队首删除元素（pop(0)）时，需要将后面的所有元素都往前移动一位，时间复杂度是O(n)，n是列表中元素的个数。 当列表很长时，这个操作会非常耗时。deque的优势：deque使用链表实现，在队首和队尾添加和删除元素的时间复杂度都是O(1)。 也就是说，不管队列有多长，这些操作都非常快。
这就像你搬家，list是让所有人帮你一起搬，每个人都得挪动一次，而deque是用了传送带，东西直接嗖嗖嗖就过去了。
为了更直观地展示deque和list在性能上的差异，我们来做一个简单的测试：
import time
from collections import deque
def test_list_pop_left(n):
my_list = list(range(n))
start_time = time.time()
for _ in range(n):
my_list.pop(0)
end_time = time.time()
return end_time - start_time
def test_deque_pop_left(n):
my_deque = deque(range(n))
start_time = time.time()
for _ in range(n):
my_deque.popleft()
end_time = time.time()
return end_time - start_time
n = 10000
list_time = test_list_pop_left(n)
deque_time = test_deque_pop_left(n)
print(f"List pop(0) time: {list_time:.6f} seconds")
print(f"Deque popleft() time: {deque_time:.6f} seconds")运行结果会显示，当n比较大时，deque的效率远高于list。
deque的基本用法
说了这么多，咱们来实际操作一下deque。 首先，你需要导入deque：
from collections import deque创建一个deque对象：
my_deque = deque() # 创建一个空的deque
my_deque = deque([1, 2, 3]) # 创建一个包含初始元素的deque常用的方法：
append(x): 在队尾添加元素x。appendleft(x): 在队首添加元素x。pop(): 移除并返回队尾的元素。 如果队列为空，会抛出IndexError。popleft(): 移除并返回队首的元素。 如果队列为空，会抛出IndexError。extend(iterable): 从队尾添加iterable中的所有元素。extendleft(iterable): 从队首添加iterable中的所有元素。 注意，添加的顺序与iterable中的顺序相反。rotate(n): 将队列中的元素向右循环移动n步。 如果n是负数，则向左循环移动。clear(): 移除队列中的所有元素。maxlen:deque可以指定最大长度。 当队列已满时，再添加元素，会自动从另一端移除元素。 这是一个可选参数，在创建deque对象时指定。
下面是一些示例代码：
from collections import deque
my_deque = deque([1, 2, 3])
my_deque.append(4)
print(my_deque) # 输出: deque([1, 2, 3, 4])
my_deque.appendleft(0)
print(my_deque) # 输出: deque([0, 1, 2, 3, 4])
last_element = my_deque.pop()
print(last_element) # 输出: 4
print(my_deque) # 输出: deque([0, 1, 2, 3])
first_element = my_deque.popleft()
print(first_element) # 输出: 0
print(my_deque) # 输出: deque([1, 2, 3])
my_deque.extend([5, 6, 7])
print(my_deque) # 输出: deque([1, 2, 3, 5, 6, 7])
my_deque.extendleft([8, 9, 10])
print(my_deque) # 输出: deque([10, 9, 8, 1, 2, 3, 5, 6, 7])
my_deque.rotate(2) # 向右移动2步
print(my_deque) # 输出: deque([6, 7, 10, 9, 8, 1, 2, 3, 5])
my_deque.rotate(-3) # 向左移动3步
print(my_deque) # 输出: deque([9, 8, 1, 2, 3, 5, 6, 7, 10])
my_deque.clear()
print(my_deque) # 输出: deque([])
limited_deque = deque(maxlen=3)
limited_deque.append(1)
limited_deque.append(2)
limited_deque.append(3)
print(limited_deque) # 输出: deque([1, 2, 3], maxlen=3)
limited_deque.append(4) # 添加元素，会移除队首的元素
print(limited_deque) # 输出: deque([2, 3, 4], maxlen=3)deque与滑动窗口
好了，铺垫了这么多，终于要进入正题了。 deque最常见的应用场景之一就是处理滑动窗口问题。
什么是滑动窗口？
滑动窗口就像一个固定大小的窗口，在数据序列上滑动。 每次滑动，窗口都会包含序列中连续的一部分数据。 我们需要对窗口中的数据进行处理，然后将窗口向后滑动。
举个例子，假设有一个数组 [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小为3。 那么滑动窗口的过程如下：
| 窗口位置 | 窗口内容 |
|---|---|
| 1, 2, 3 | [1, 3, -1] |
| 2, 3, 4 | [3, -1, -3] |
| 3, 4, 5 | [-1, -3, 5] |
| 4, 5, 6 | [-3, 5, 3] |
| 5, 6, 7 | [5, 3, 6] |
| 6, 7, 8 | [3, 6, 7] |
滑动窗口的常见问题
滑动窗口问题有很多变种，常见的有：
- 求滑动窗口的最大值/最小值
- 求滑动窗口的平均值
- 求滑动窗口中满足特定条件的元素个数
如何用deque解决滑动窗口问题？
deque非常适合解决滑动窗口的最大值/最小值问题。 它的核心思想是：维护一个deque，其中存储的是可能成为最大值/最小值的元素的索引。
以求滑动窗口最大值为例，假设窗口大小为k：
- 初始化： 创建一个空的
deque。 - 遍历数组：
- 移除过期元素： 如果
deque队首元素的索引小于i - k + 1(i是当前元素的索引)，说明队首元素已经不在当前窗口内，需要从队首移除。 - 维护
deque的单调性： 从队尾开始，移除所有小于当前元素的元素的索引。 这样可以保证deque中的元素是单调递减的（从队首到队尾）。 - 添加当前元素： 将当前元素的索引添加到队尾。
- 记录最大值： 当窗口滑动到有效位置（
i >= k - 1）时，deque的队首元素就是当前窗口的最大值。
- 移除过期元素： 如果
是不是有点绕？ 没关系，咱们来看代码：
from collections import deque
def max_sliding_window(nums, k):
"""
使用deque求滑动窗口的最大值
"""
if not nums or k <= 0:
return []
n = len(nums)
result = []
window = deque() # 存储索引
for i in range(n):
# 移除过期元素
while window and window[0] <= i - k:
window.popleft()
# 维护deque的单调性
while window and nums[window[-1]] <= nums[i]:
window.pop()
# 添加当前元素
window.append(i)
# 记录最大值
if i >= k - 1:
result.append(nums[window[0]])
return result
# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
max_values = max_sliding_window(nums, k)
print(f"滑动窗口最大值：{max_values}") # 输出: 滑动窗口最大值：[3, 3, 5, 5, 6, 7]这段代码的核心在于维护deque的单调性。 deque中始终存储的是当前窗口中可能成为最大值的元素的索引。 当遇到更大的元素时，就把deque中小于它的元素都移除，确保deque的队首元素始终是当前窗口的最大值。
代码解释：
if not nums or k <= 0:: 处理输入为空或窗口大小不合法的情况。window = deque(): 创建一个空的deque，用于存储索引。while window and window[0] <= i - k:: 检查deque的队首元素是否过期。 如果队首元素的索引小于i - k + 1，说明它已经不在当前窗口内，需要移除。while window and nums[window[-1]] <= nums[i]:: 维护deque的单调性。 从队尾开始，移除所有小于当前元素的元素的索引。 这样可以保证deque中的元素是单调递减的。window.append(i): 将当前元素的索引添加到队尾。if i >= k - 1:: 当窗口滑动到有效位置时，deque的队首元素就是当前窗口的最大值。
举一反三：求滑动窗口的最小值
求滑动窗口的最小值与求最大值的思路类似，只需要将deque维护成单调递增的即可。 代码如下：
from collections import deque
def min_sliding_window(nums, k):
"""
使用deque求滑动窗口的最小值
"""
if not nums or k <= 0:
return []
n = len(nums)
result = []
window = deque() # 存储索引
for i in range(n):
# 移除过期元素
while window and window[0] <= i - k:
window.popleft()
# 维护deque的单调性
while window and nums[window[-1]] >= nums[i]: # 注意这里的比较符号
window.pop()
# 添加当前元素
window.append(i)
# 记录最小值
if i >= k - 1:
result.append(nums[window[0]])
return result
# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
min_values = min_sliding_window(nums, k)
print(f"滑动窗口最小值：{min_values}") # 输出: 滑动窗口最小值：[-1, -3, -3, -3, 3, 3]唯一的区别在于while window and nums[window[-1]] >= nums[i]: 这一行，将比较符号从<=改为了>=， 从而保证deque中的元素是单调递增的。
deque的其他应用场景
除了滑动窗口，deque还有很多其他的应用场景：
- 实现循环队列：
deque可以方便地实现循环队列，用于解决生产者-消费者问题等。 - 历史记录： 可以使用
deque来保存最近访问的URL，实现浏览器的历史记录功能。 - 回文判断： 可以使用
deque来判断一个字符串是否是回文串。
总结
collections.deque是一个非常实用的数据结构，它具有高效的队首和队尾操作，非常适合解决滑动窗口问题以及其他需要频繁在两端进行添加和删除操作的场景。 掌握deque的用法，可以让你在编写Python代码时更加得心应手。
希望今天的讲座对大家有所帮助！ 记住，编程就像相声，三分逗，七分捧。 deque就是那个默默无闻的捧哏，关键时刻总能给你意想不到的惊喜。 感谢大家的收听，咱们下次再见！