当前位置：首页 > 文章列表 > 文章 > python教程 > 滑动窗口min/max时间复杂度解析

滑动窗口min/max时间复杂度解析

2026-03-13 13:57:35 0浏览收藏

本文深入剖析了滑动窗口问题中一个常见却极易踩坑的低效实现——直接在切片上调用min()和max()导致最坏时间复杂度飙升至O(n³)，并通过严谨的逐层复杂度分析揭示其根源在于重复全量扫描；随后给出基于双端队列的优雅O(n)标准解法，利用单调队列增量维护窗口极值，每个元素仅入队出队一次，真正实现高效滑动；文章不仅提供可直接复用的代码，更强调算法设计的核心思维：避免重复计算、关注操作粒度、用数据结构承载状态演化——帮你彻底避开初学者陷阱，写出既正确又高性能的滑动窗口代码。

滑动窗口中重复调用 min/max 的时间复杂度深度分析

本文剖析一段典型但低效的滑动窗口实现，指出其 min() 和 max() 在切片上重复计算导致最坏时间复杂度达 $O(n^3)$，并给出优化至 $O(n)$ 的标准解法。

本文剖析一段典型但低效的滑动窗口实现，指出其 min() 和 max() 在切片上重复计算导致最坏时间复杂度达 $O(n^3)$，并给出优化至 $O(n)$ 的标准解法。

该代码试图求解「最长子数组，满足最大值与最小值之差不超过 limit」，但其实现方式存在严重性能缺陷。核心问题在于：每次调用 max(nums[left:right+1]) 或 min(nums[left:right+1]) 都需遍历当前子数组，时间复杂度为 $O(\text{window_length})$。而外层 for right in range(n) 与内层 while 循环共同构成嵌套结构，导致实际复杂度远超直观预期。

我们逐层分析：

外层 for right 循环执行 $n$ 次；
对每个 right，最坏情况下 while 循环可能将 left 从 0 逐步推进到 right（即尝试所有左端点），共 $O(n)$ 次迭代；
每次迭代中，max() 和 min() 均在长度为 $O(n)$ 的切片上执行，耗时 $O(n)$；

因此，总时间复杂度为：
$$ \sum{\text{right}=0}^{n-1} \sum{\text{left}=0}^{\text{right}} O(\text{right} - \text{left} + 1) = O(n^3) $$
这正是答案所指出的 $O(n^3)$ 最坏情况——例如输入为严格递增数组且 limit=0 时，每次窗口扩展后都需重算全量极值，并反复收缩左边界。

更关键的是，这段代码并非标准滑动窗口：真正的滑动窗口应维护窗口状态的增量更新（如单调队列或堆），而非每次都重新扫描子数组。以下是推荐的 $O(n)$ 解法（使用双端队列维护滑动窗口最大/最小值）：

from collections import deque

def longestSubarray(nums, limit):
    max_q = deque()  # 单调递减：队首为当前窗口最大值
    min_q = deque()  # 单调递增：队首为当前窗口最小值
    left = 0
    max_len = 0

    for right in range(len(nums)):
        # 维护 max_q（递减）
        while max_q and nums[max_q[-1]] < nums[right]:
            max_q.pop()
        max_q.append(right)

        # 维护 min_q（递增）
        while min_q and nums[min_q[-1]] > nums[right]:
            min_q.pop()
        min_q.append(right)

        # 收缩窗口直到满足条件
        while nums[max_q[0]] - nums[min_q[0]] > limit:
            if max_q[0] == left:
                max_q.popleft()
            if min_q[0] == left:
                min_q.popleft()
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

✅ 优势说明：