这段带有滑动窗口的代码的时间复杂度是多少？

Question

父 for 循环有 On ，而 while 循环有摊销 O n ？意思是我们认为它是O 1？还 最小和最大操作它们将是好的，但在最坏的情况下又会再次打开？ 是O(n^3)吗？

        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

我正在评估这个的时间复杂度

Answer 1

由于嵌套循环结构和重复的

O(n^2)

/

min()

调用，最坏情况的时间复杂度似乎超过了

max()

。在

O(n^3)

循环频繁重置

while

并且最大/最小值是在大切片上计算的情况下，它可能会接近

left

。