一、什么是滑动窗口？

滑动窗口是一种使用双指针维护数组/字符串区间的算法技巧。它通过动态调整窗口的左右边界，在 O(n) 时间内解决子数组/子串相关问题，避免暴力枚举的 O(n²) 复杂度

核心思想
用两个指针 left 和 right 定义一个窗口 [left, right)，通过移动指针来扩大或缩小窗口：

• 扩大窗口：移动 right，将新元素纳入窗口
• 缩小窗口：移动 left，将过期元素移出窗口

两种类型

类型	特点	典型问题
定长窗口	窗口大小固定，直接平移	滑动窗口最大值/最小值、大小为k的子数组和
变长窗口	窗口大小动态变化，根据条件调整	满足条件的最短/最长子数组

时间复杂度对比

方法	复杂度	说明
暴力枚举	O(n²) 或 O(n³)	枚举所有子数组，重复计算
滑动窗口	O(n)	每个元素最多进窗口一次、出窗口一次

二、滑动窗口通用代码模板

模板1：定长滑动窗口

// 定长滑动窗口：维护大小为k的窗口
int fixedWindow(vector<int>& nums, int k) {
    int n = nums.size();
    if (n < k) return 0;
    
    // 1. 计算第一个窗口
    int window_sum = 0;
    for (int i = 0; i < k; i++) {
        window_sum += nums[i];
    }
    int ans = window_sum;
    
    // 2. 窗口滑动
    for (int i = k; i < n; i++) {
        window_sum += nums[i] - nums[i - k];  // 新元素进，旧元素出
        ans = max(ans, window_sum);
    }
    return ans;
}

模板2：变长滑动窗口（求最短/最小）

// 变长滑动窗口：寻找满足条件的最短子数组
int variableWindow(vector<int>& nums, int target) {
    int left = 0, window_sum = 0, ans = INT_MAX;
    
    for (int right = 0; right < nums.size(); right++) {
        window_sum += nums[right];  // 扩大窗口
        
        // 当窗口满足条件时，尝试缩小窗口寻找更优解
        while (window_sum >= target) {
            ans = min(ans, right - left + 1);
            window_sum -= nums[left];
            left++;
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

模板3：变长滑动窗口（配合哈希表，处理子串问题）

// 变长滑动窗口 + 哈希表：处理子串匹配问题
int stringWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;  // 已匹配上的字符种类数
    
    while (right < s.size()) {
        char c = s[right];
        right++;
        
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        
        // 当窗口满足条件时，尝试收缩左边界
        while (valid == need.size()) {
            // 更新答案
            
            char d = s[left];
            left++;
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return ans;
}

三、定长滑动窗口（洛谷 + 牛客）

3.1 滑动窗口最大值/最小值（洛谷 P1886 / 牛客 NC50528）

题目描述：给定一个长度为 n 的数组和一个大小为 k 的窗口，窗口从最左端滑到最右端，求每个位置窗口内的最大值和最小值。
输入示例：
8 3
1 3 -1 -3 5 3 6 7
输出示例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
解题思路：

• 使用单调队列（双端队列）维护窗口内的最值
• 队列存放下标，保持队列中元素对应的值单调递增/递减
• 队首元素即为当前窗口的最值

代码如下：

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e6 + 10;
int a[N], q[N];  // q 存储下标

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // 求最小值（单调递增队列）
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        // 移除超出窗口范围的元素
        if (hh <= tt && i - q[hh] >= k) hh++;
        
        // 维护单调性：队列中元素对应的值单调递增
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        
        // 窗口形成后输出
        if (i >= k - 1) cout << a[q[hh]] << " ";
    }
    cout << endl;
    
    // 求最大值（单调递减队列）
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - q[hh] >= k) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) cout << a[q[hh]] << " ";
    }
    
    return 0;
}

复杂度分析：每个元素最多入队、出队一次，时间复杂度 O(n)，空间复杂度 O(n)。
相关题目链接：
P1886 【模板】单调队列 / 滑动窗口 – 洛谷
滑动窗口

四、变长滑动窗口

4.1 长度最小的子数组（LeetCode 209）

题目描述：给定一个含有 n 个正整数的数组和一个正整数 target，找出和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在，返回 0。
输入示例：nums = [2,3,1,2,4,3], target = 7 → 输出 2（子数组 [4,3]）
解题思路：
重复直到 right 到达数组末尾
右指针 right 向右扩展窗口，累加和
当窗口和 ≥ target 时，记录长度并尝试移动左指针缩小窗口

代码：

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, sum = 0, ans = INT_MAX;
    
    for (int right = 0; right < nums.size(); right++) {
        sum += nums[right];  // 扩大窗口
        
        // 当满足条件时，尝试缩小窗口
        while (sum >= target) {
            ans = min(ans, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    
    return ans == INT_MAX ? 0 : ans;
}

五、滑动窗口 + 哈希表（子串匹配类）

5.1 最小覆盖子串（LeetCode 76）
题目描述：给定字符串 s 和 t，返回 s 中包含 t 所有字符的最小子串。
输入示例：s = "ADOBECODEBANC", t = "ABC" → 输出 "BANC"
解题思路：
用 need 哈希表记录 t 中每个字符的需求量
用 window 哈希表记录当前窗口中的字符数量
valid 记录已满足需求的字符种类数
当 valid == need.size() 时，窗口满足条件，尝试收缩

代码：

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;
    int start = 0, min_len = INT_MAX;
    
    while (right < s.size()) {
        char c = s[right];
        right++;
        
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        
        // 窗口满足条件，尝试收缩
        while (valid == need.size()) {
            if (right - left < min_len) {
                start = left;
                min_len = right - left;
            }
            
            char d = s[left];
            left++;
            
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    
    return min_len == INT_MAX ? "" : s.substr(start, min_len);
}

六、滑动窗口进阶：单调队列优化

当滑动窗口需要动态维护窗口内的最大值/最小值时，普通滑动窗口 O(n·k) 的复杂度不够高效，需要用单调队列优化到 O(n)。

单调队列的核心操作：
维护单调性：新元素入队时，从队尾弹出所有比它小（维护递减队列）或比它大（维护递增队列）的元素
维护窗口范围：队首元素如果超出窗口范围，从队首弹出
获取当前窗口最值：队首元素即为窗口内的最值

模板代码（以最大值为例）：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // 存储下标，队首到队尾单调递减
    vector<int> ans;
    
    for (int i = 0; i < nums.size(); i++) {
        // 1. 移除超出窗口范围的元素
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        
        // 2. 维护单调性：队尾元素 < 当前元素则弹出
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        
        // 3. 窗口形成后，记录结果
        if (i >= k - 1) {
            ans.push_back(nums[dq.front()]);
        }
    }
    return ans;
}

七、经典例题