滑动窗口求k长子数组最大值的算法时间复杂度是O(n)还是O(n²)?

你提供的代码时间复杂度为O(nk)，当k趋近于数组长度n时，最坏复杂度为O(n²)，你之前认为的O(n)是错误的。

复杂度计算依据 #

• 外层循环次数为 len(arr) - k + 1，量级为O(n)
• 每次循环内的两个操作都是O(k)耗时：
  1. Python列表切片arr[i:j]需要复制区间内的所有k个元素，时间复杂度为O(k)
  2. max(sub_arr)需要遍历长度为k的子数组的所有元素求最大值，时间复杂度为O(k)
• 整体时间复杂度为两者相乘：O(n) * O(k) = O(nk)

补充说明 #

你当前的实现本质是暴力枚举所有窗口再逐个求最大值，不属于优化后的滑动窗口算法。真正O(n)时间复杂度的滑动窗口解法需要借助单调双端队列实现：维护队列中存储的是当前窗口内可能成为最大值的元素下标，保证队列内元素对应的值单调递减，每个元素最多入队、出队各1次，全程不需要做数组切片，也不需要每次遍历整个窗口求最大值，整体时间复杂度才是O(n)。

你提供的代码格式化后如下：

class Solution:
    def maximum_of_all_subarrays_of_size_k(self,arr,k):
        j = k
        overall_max = float('-inf')
        for i in range(0, len(arr)-k+1):
            sub_arr = arr[i:j]
            print(f"maximum of current {sub_arr} is {max(sub_arr)}")
            current_max = max(sub_arr)
            overall_max = max(overall_max, current_max)
            j+=1
        return overall_max

if __name__ == "__main__":
    sol = Solution()
    arr = [8, 5, 10, 7, 9, 4, 15, 12, 90, 13] 
    k = 3
    print(sol.maximum_of_all_subarrays_of_size_k(arr,k))

内容的提问来源于stack exchange，提问作者Muhammad Mustafa