如何高效计算Python中滑动序列的最大/最小值？

要实现滑动窗口最大/最小值的最高效方案，首推单调双端队列，整体时间复杂度为O(n)，比你提到的max()（每次窗口移动耗时O(k)，k为窗口大小）和heapq（存在元素删除的额外开销）都更高效。

核心原理 #

用collections.deque维护一个队列，队列中存储窗口内元素的索引（而非值，方便判断元素是否滑出窗口），并保持队列的单调性：

• 求最大值时，队列保持单调递减：新元素进入窗口时，从队尾移除所有比当前元素小的元素——这些元素不可能成为后续窗口的最大值
• 求最小值时，队列保持单调递增：新元素进入窗口时，从队尾移除所有比当前元素大的元素
• 每次窗口移动后，检查队首索引是否已滑出窗口左边界，若是则弹出队首
• 此时队首对应的元素就是当前窗口的极值

代码实现 #

滑动窗口最大值 #

from collections import deque

def sliding_window_max(nums, k):
    q = deque()
    result = []
    for i, num in enumerate(nums):
        # 移除队尾所有比当前元素小的元素
        while q and nums[q[-1]] < num:
            q.pop()
        q.append(i)
        # 移除窗口外的过期元素
        while q[0] <= i - k:
            q.popleft()
        # 窗口形成后开始记录结果
        if i >= k - 1:
            result.append(nums[q[0]])
    return result

滑动窗口最小值 #

只需调整队尾的判断逻辑，保持队列单调递增即可：

def sliding_window_min(nums, k):
    q = deque()
    result = []
    for i, num in enumerate(nums):
        # 移除队尾所有比当前元素大的元素
        while q and nums[q[-1]] > num:
            q.pop()
        q.append(i)
        # 移除窗口外的过期元素
        while q[0] <= i - k:
            q.popleft()
        # 窗口形成后记录结果
        if i >= k - 1:
            result.append(nums[q[0]])
    return result

各方法效率对比 #

• max()/min()：每次窗口移动都要遍历整个窗口，时间复杂度O(nk)，窗口越大效率越低，仅适合极小窗口场景
• heapq：理论单次操作O(logk)，但Python的heapq是最小堆，求最大值需存负值；且元素滑出窗口时无法直接删除堆中对应元素，只能标记后忽略，会导致堆体积膨胀，实际效率接近O(nlogn)
• 单调队列：每个元素仅入队、出队一次，整体O(n)时间复杂度，是滑动窗口极值问题的最优解法

内容的提问来源于stack exchange，提问作者jean-leo