LeetCode 滑动窗口算法总结：从入门到精通

引言

滑动窗口是一种常用的算法技巧，特别适合处理数组或字符串的连续子序列问题。本文将深入探讨滑动窗口算法的基本概念、常见类型、应用场景以及在 LeetCode 上的实际应用。

1. 滑动窗口算法概述

滑动窗口算法的核心思想是维护一个可变大小的”窗口”，通过同时移动这个窗口的左右边界，高效地遍历数组或字符串，从而在线性时间内解决一些复杂的子序列问题。

2. 滑动窗口的基本框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def sliding_window(s):
    left = right = 0
    window = {}  # 用于存储窗口中的元素
    result = 0   # 根据具体问题而定的结果变量

    while right < len(s):
        # 扩大窗口
        c = s[right]
        window[c] = window.get(c, 0) + 1
        right += 1

        # 根据条件收缩窗口
        while window_needs_shrink():
            d = s[left]
            window[d] -= 1
            if window[d] == 0:
                del window[d]
            left += 1

        # 更新结果
        result = max(result, right - left)

    return result

3. 常见滑动窗口问题类型

3.1 固定大小窗口

这类问题要求在固定大小的窗口内进行操作。

示例：LeetCode 643. Maximum Average Subarray I

1
2
3
4
5
6
7
8
9
def findMaxAverage(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum = window_sum - nums[i-k] + nums[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum / k

3.2 可变大小窗口

这类问题允许窗口大小动态变化，以满足特定条件。

示例：LeetCode 3. Longest Substring Without Repeating Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
def lengthOfLongestSubstring(s):
    char_index = {}
    max_length = 0
    start = 0
    
    for end, char in enumerate(s):
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        else:
            max_length = max(max_length, end - start + 1)
        char_index[char] = end
    
    return max_length

4. 高级滑动窗口技巧

4.1 双指针 + 哈希表

结合使用双指针和哈希表可以高效地解决一些复杂的滑动窗口问题。

示例：LeetCode 76. Minimum Window Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from collections import Counter

def minWindow(s, t):
    need = Counter(t)
    window = Counter()
    left = right = 0
    valid = 0
    start, min_len = 0, float('inf')

    while right < len(s):
        c = s[right]
        right += 1
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1
        
        while valid == len(need):
            if right - left < min_len:
                start = left
                min_len = right - left
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return '' if min_len == float('inf') else s[start:start+min_len]

4.2 滑动窗口 + 单调队列

结合使用滑动窗口和单调队列可以解决一些特殊的窗口最大值/最小值问题。

示例：LeetCode 239. Sliding Window Maximum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque

def maxSlidingWindow(nums, k):
    result = []
    window = deque()
    
    for i, num in enumerate(nums):
        if window and window[0] <= i - k:
            window.popleft()
        while window and nums[window[-1]] < num:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    
    return result

5. 滑动窗口解题技巧

  1. 明确窗口: 确定窗口的定义和含义，这决定了如何移动和维护窗口。

  2. 选择合适的数据结构: 根据问题特点选择合适的数据结构来维护窗口，常用的有哈希表、队列等。

  3. 窗口的扩展与收缩: 明确何时扩大窗口，何时收缩窗口，以及如何更新窗口内的信息。

  4. 结果更新: 在适当的时机更新结果，可能是在窗口扩展时，也可能是在窗口收缩时。

  5. 边界条件处理: 注意处理特殊情况，如空字符串、窗口大小超过字符串长度等。

6. 滑动窗口的应用场景

  1. 子串问题: 查找满足特定条件的子串。
  2. 子数组问题: 寻找满足特定条件的子数组。
  3. 字符串匹配: 在较长的字符串中查找模式串。
  4. 数据流处理: 处理连续到达的数据流。

7. 滑动窗口的优化思路

  1. 预处理: 对于某些问题，可以先对数据进行预处理，如计算前缀和，这样可以在常数时间内得到任意区间的和。

  2. 双指针优化: 在某些情况下，可以使用双指针技巧来优化滑动窗口算法，减少不必要的操作。

  3. 空间优化: 对于固定大小的窗口，有时可以只维护必要的信息，而不需要存储整个窗口的内容。

  4. 单调性优化: 利用问题的单调性质，可以使用单调队列或单调栈来优化某些操作。

8. 滑动窗口的局限性

尽管滑动窗口算法强大而灵活，但也存在一些局限性：

  1. 适用范围: 主要适用于处理连续子序列的问题，对于非连续的问题可能不适用。

  2. 复杂度: 虽然通常可以将时间复杂度优化到 O(n)，但空间复杂度可能较高，特别是需要维护大量信息的情况。

  3. 实现复杂度: 某些滑动窗口问题的实现可能比较复杂，需要仔细处理各种边界情况。

  4. 不适合处理全局最优: 滑动窗口主要关注局部信息，对于需要考虑全局信息的问题可能不太适用。

结语

滑动窗口算法是一种强大的技巧，特别适合解决子串、子数组相关的问题。通过本文的学习，我们了解了滑动窗口的基本概念、常见类型、应用场景以及各种高级技巧。在实际应用中，要根据具体问题的特点，选择合适的滑动窗口策略，并结合其他数据结构和算法技巧来优化解决方案。通过不断练习和总结，我们可以在算法解题中越来越熟练地运用滑动窗口技巧，解决各种复杂的序列处理问题。