python标准库--collections - 高性能数据结构在算法比赛的应用

目录

一、deque双端队列

1.头部删除元素popleft（）

2.BFS（广度优先搜索）优化

3.滑动窗口（双指针）

4.实现栈或队列

5. 双向遍历与操作

一、deque双端队列

• 特点：支持两端 O (1) 时间复杂度的添加和删除操作，比列表（list）的左端操作（如list.insert(0, x)）高效得多。
• 常用方法：
  • append(x)/appendleft(x)：右端 / 左端添加元素。
  • pop()/popleft()：右端 / 左端删除元素。
  • rotate(n)：循环移动元素（n>0右移，n<0左移）。
  • maxlen：固定队列长度（超出时自动删除对侧元素）。
• 参数：初始化时可传入迭代对象，如deque([1,2,3])，或指定maxlen=5。
• 优点：
  • 高效处理队列（FIFO）和栈（LIFO）场景。
  • 滑动窗口场景中，可快速维护窗口内元素（如删除过期元素）

1.头部删除元素popleft（）

import time
from collections import deque
list1 = list(range(1000_0000))
X1 = time.time()
for _ in range(1000):
    list1.pop(0)
print(time.time()-X1)

list2 = deque(range(1000_0000))
X1= time.time()
for _ in range(1000):
    list2.popleft()
print(time.time()-X1)
#8.393102645874023
#0.0恐怖

2.BFS（广度优先搜索）优化

在 BFS 中，需要频繁从队列头部弹出元素、从尾部添加元素。deque的popleft()操作时间复杂度为 O (1)，比列表的pop(0)更高效（列表的pop(0)是 O (n)）。

实例：二叉树遍历

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root):
    if not root:
        return []
    queue = deque([root])  # 初始化队列
    result = []
    while queue:
        node = queue.popleft()  # O(1) 弹出队首元素
        result.append(node.val)
        if node.left:
            queue.append(node.left)  # O(1) 添加到队尾
        if node.right:
            queue.append(node.right)
    return result

3.滑动窗口（双指针）

from collections import deque

def maxSlidingWindow(nums, k):
    result = []
    window = deque()  # 存储索引
    for i in range(len(nums)):
        # 移除窗口外的元素
        if window and window[0] <= i - k:
            window.popleft()
        # 保持队列单调递减
        while window and nums[window[-1]] < nums[i]:
            window.pop()
        window.append(i)
        # 窗口形成后记录最大值
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

4.实现栈或队列

from collections import deque

class MyQueue:
    def __init__(self):
        self.queue = deque()
    
    def push(self, x):
        self.queue.append(x)  # O(1)
    
    def pop(self):
        return self.queue.popleft()  # O(1)
    
    def peek(self):
        return self.queue[0]
    
    def empty(self):
        return len(self.queue) == 0

5. 双向遍历与操作

from collections import deque

def isPalindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():  # 两端同时弹出比较
            return False
    return True