带滑动窗口的Python代码时间复杂度分析咨询

问题拆解与分析： #

1. 外层for循环与while循环的摊还复杂度
   外层for循环的迭代次数是O(n)，因为right会遍历数组的每个元素（共n个）。
   while循环中，left变量只会单调递增，从0到n-1的总移动次数最多是n次——也就是说，整个代码执行过程中，while循环的总执行次数是O(n)，分摊到外层的n次循环中，每次外层循环对应的while操作摊还复杂度是O(1)。

2. min/max操作的时间复杂度
   每次调用max(nums[left:right+1])或min(nums[left:right+1])，都需要遍历从left到right的整个子数组，这个操作的时间复杂度是O(k)，其中k是当前窗口的长度（right-left+1）。最坏情况下，窗口长度可以达到n（比如left一直为0，right走到数组末尾），此时单次min/max操作的复杂度是O(n)。

3. 整体时间复杂度
   结合上面两点来看，最坏情况下的总复杂度确实是O(n³)：

• 假设limit极小，每次right移动后，都需要将left从0逐步移动到right位置才能满足窗口条件。
• 此时，所有min/max操作对应的窗口长度之和为：1 + (2+1) + (3+2+1) + ... + (n-1 + n-2 + ... +1)，这个求和结果是O(n³)量级的——因为每一项是k(k+1)/2，求和后等价于O(n³)。
• 因此，整体时间复杂度为O(n³)。

附原代码： #

left=0
curr_max=0
for right in range(len(nums)):
    mx =max(nums[left:right+1])
    mn =min(nums[left:right+1])
    if mx - mn <=limit:
        curr_max = max(right - left + 1,curr_max)
    while  mx - mn > limit:
        left+=1
        if max(nums[left:right+1]) - min(nums[left:right+1]) <=limit:
            curr_max = max(right - left + 1,curr_max)
            break
# print(curr_max)
return curr_max

内容的提问来源于stack exchange，提问作者faber soaks