滑动窗口内层循环时间复杂度疑问——以LeetCode 1838题为例

题目背景 #

LeetCode题目1838. Frequency of the Most Frequent Element：定义元素的frequency为其在数组中的出现次数，给定整数数组nums和整数k，每次操作可将数组中某元素加1，求最多执行k次操作后元素的最大可能frequency。

滑动窗口解法代码 #

def maxFrequency(self, nums: List[int], k: int) -> int:
    nums.sort()
    res, curSum = 0, 0
    l = 0
    for r in range(len(nums)):
        total = nums[r] * (r - l + 1)  # the goal
        curSum += nums[r]  # what we currently have

        # check if we have enough operations to reach our goal
        while total - curSum > k:
            # remove L until we have valid subsequence
            curSum -= nums[l]
            l += 1
            total = nums[r] * (r - l + 1)
 
        res = max(res, r - l + 1)
    
    return res

疑问点 #

论坛称该解法时间复杂度为O(nlogn)，瓶颈在nums的排序，但无法理解计算逻辑。原以为外层for循环复杂度为O(n)，内层while循环最坏为O(n)，总复杂度应为O(nlogn)+O(n²)=O(n²)，想知道为何内外循环的总时间复杂度是O(n)而非O(n²)？

时间复杂度分析 #

关键在于滑动窗口的左右指针只会单向移动：

• 外层for循环中，右指针r从0到n-1，总共移动n次，全程向前不回头。
• 内层while循环里，左指针l只会从当前位置向右移动，不会向左后退。整个算法过程中，l最多从0走到n-1，总共移动n次。

也就是说，内外循环加起来，r和l的总移动次数是2n，属于O(n)级别的操作。不会出现外层每走一次，内层就走n次的极端情况——因为l一旦右移，后续r增大时，l不会回到之前的位置，不会重复处理相同元素。

因此，滑动窗口的操作时间复杂度是O(n)，加上排序的O(nlogn)，总复杂度就是O(nlogn)，瓶颈确实在排序步骤。

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