如何高效统计滑动窗口中最大两数之和符合要求的窗口数量

你当前逐窗口排序的方案时间复杂度为O(nk logk)，在数据规模较大时会出现性能瓶颈，以下两种方案可以大幅提升效率：

方案1：有序集合实现（逻辑简单易写） #

• 时间复杂度：O(n logk)，空间复杂度：O(k)
• 实现步骤：
  • 初始化可存储重复元素的有序集合，先将数组前k个元素加入集合
  • 每次直接取集合末尾最大的两个元素求和，和大于阈值时计数加1
  • 窗口右移时，先删除离开窗口的左边界元素，再加入新进入窗口的右边界元素，重复上述求和判断逻辑即可
• 适用场景：面试时允许使用语言内置/第三方有序容器的场景，比如C++的multiset、Python的SortedList

方案2：双单调队列实现（性能最优无依赖） #

• 时间复杂度：O(n)，空间复杂度：O(k)
• 实现步骤：
  • 维护两个单调递减的双端队列，分别存储当前窗口内第一大、第二大元素的下标，队列头部始终为对应排名的元素下标
  • 新元素入队时，弹出队尾所有对应值小于当前元素的下标，保证队列单调递减
  • 窗口右移时，先判断队列头部下标是否超出窗口左边界，超出则弹出队头
  • 每次取两个队列头部对应的元素值求和判断是否符合要求即可
• 适用场景：不允许使用额外有序容器的面试场景，是该题的最优解

from sortedcontainers import SortedList

def count_valid_windows(nums: list[int], k: int, threshold: int) -> int:
    sorted_win = SortedList()
    res = 0
    left = 0
    for right in range(len(nums)):
        sorted_win.add(nums[right])
        # 窗口长度达到k时开始判断
        if right - left + 1 == k:
            # 取最大两个元素求和
            if sorted_win[-1] + sorted_win[-2] > threshold:
                res += 1
            # 移除左边界元素后窗口右移
            sorted_win.remove(nums[left])
            left += 1
    return res

# 测试题目示例
nums = [1,3,-1,-3,5,3,6,7]
k = 3
threshold = 7
print(count_valid_windows(nums, k, threshold)) # 输出3

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