LeetCode239滑动窗口最大值解法错误排查及优化咨询

原逻辑的核心漏洞 #

仅维护单个maxSoFar和secondMaxSoFar的思路存在两个致命问题：

• 当窗口内存在多个相同的最大值时，滑出一个最大值后，剩余窗口仍有该最大值，但原逻辑会错误地将maxSoFar替换为secondMaxSoFar
• secondMaxSoFar可能已经滑出窗口，或者窗口内存在比secondMaxSoFar更大的次值，此时依赖secondMaxSoFar更新maxSoFar会导致错误

基于原思路的优化方案 #

不需要更换数据结构，只需要在原逻辑基础上增加最大值计数，并在必要时重新扫描窗口即可解决问题：

1. 维护maxSoFar记录当前窗口最大值，同时用countMax记录该最大值在窗口内的出现次数
2. 滑动窗口时，先处理滑出的元素：如果滑出的是maxSoFar，则减少countMax；当countMax变为0时，重新扫描当前窗口获取新的maxSoFar和countMax
3. 处理新加入的元素：如果新元素大于maxSoFar，则更新maxSoFar并重置countMax为1；如果等于maxSoFar，则增加countMax

优化后的Python代码 #

def maxSlidingWindow(nums, k):
    if not nums or k == 0:
        return []
    res = []
    
    # 初始化第一个窗口的最大值和计数
    first_window = nums[:k]
    max_so_far = max(first_window)
    count_max = first_window.count(max_so_far)
    res.append(max_so_far)
    
    for i in range(k, len(nums)):
        left_out = nums[i - k]
        new_in = nums[i]
        
        # 处理滑出窗口的元素
        if left_out == max_so_far:
            count_max -= 1
            # 当最大值全部滑出时，重新扫描当前窗口
            if count_max == 0:
                current_window = nums[i - k + 1:i + 1]
                max_so_far = max(current_window)
                count_max = current_window.count(max_so_far)
        
        # 处理新加入窗口的元素
        if new_in > max_so_far:
            max_so_far = new_in
            count_max = 1
        elif new_in == max_so_far:
            count_max += 1
        
        res.append(max_so_far)
    
    return res

方案说明 #

• 解决了重复最大值的问题：比如窗口为[5,3,5]，滑出第一个5后，countMax从2变为1，maxSoFar仍为5，无需替换为次大值
• 避免了secondMaxSoFar失效的问题：当最大值全部滑出时，重新扫描当前窗口确保获取的是最新的最大值，而非依赖可能已失效的次大值
• 保留了原思路的简洁性，未引入优先队列、单调队列等复杂数据结构，仅通过计数和必要的窗口扫描修复了逻辑漏洞

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