LeetCode滑动窗口最大值问题：两种迭代解法的时间复杂度差异及超时原因问询

Let’s break down your code first:

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    res = []
    for i in range(len(nums)-k+1):
        for j in range(i+k-1,len(nums)):
            res.append(max(nums[i:j+1]))
            break
    return res

The key issues causing your time-out: #

1. Costly list slicing: nums[i:j+1] creates an entirely new list by copying k elements every iteration. This is an O(k) operation on its own, and then calling max() on that new list adds another O(k) scan. So per window, you’re looking at O(k) time.
2. Total overhead: With n-k+1 windows, your total time complexity is *O((n-k+1)k) = O(nk). For large LeetCode test cases (where n can hit 10^5), this is way too slow—and the extra memory allocation from slicing pushes it over the time limit.

Now let’s look at the working solution:

def get_max(nums, start, end):
    answer = -2**31
    for i in range(start, end+1):
        answer = max(answer, nums[i])
    return answer

def maxSlidingWindow( nums, k):
    start,end = 0,k-1
    result = []
    while end < len(nums) and len(nums):
        result.append(self.get_max(nums, start, end))
        start, end = start+1, end+1
    return result

Why this one avoids time-out: #

Even though its theoretical time complexity is also O(nk), it cuts out the most expensive part of your code: list slicing. Instead of creating a new list every time, it iterates directly over the original array’s indices. Slicing in Python involves memory allocation and element copying—operations that are surprisingly slow compared to looping through existing elements. This reduction in overhead makes the difference between passing and timing out on tighter test cases.

A quick pro tip: Neither of these is the optimal solution for this problem. The best approach uses a monotonic deque (via collections.deque), which gets you O(n) time complexity by maintaining a queue of indices where corresponding values are in decreasing order. This lets you grab the window max in O(1) time without repeated scans.

内容的提问来源于stack exchange，提问作者if fhhf