C++ 算法技巧 — 滑动窗口 (Sliding Window)

章节概述

滑动窗口是双指针的特化形式，维护一个动态区间（窗口），在数组上平滑移动，
常用于解决满足某种性质的连续区间问题。右指针扩展纳入新元素，左指针收缩满足条件。

核心原理

1. 定长滑动窗口 — 增量更新

窗口长度固定为 k，每次右移一格，新的和 = 旧和 - 最左离开元素 + 最右进入元素。

$su{m}_i=su{m}_{i-1}-a[i-k]+a[i]$

时间复杂度 O(n)，空间 O(1)。

2. 不定长滑动窗口 — 双指针单调移动

核心框架：

l = 0
for r in 0..n-1:
    加入 a[r] 到窗口
    while (窗口不满足条件):
        移除 a[l]
        l++
    更新答案

左右指针均单调右移，每个元素最多进一次出一次，均摊 O(n)。

3. 单调队列优化 — 滑动窗口最值

用双端队列 (deque) 维护窗口最值，均摊 O(n) 而非暴力 O(nk)：

• 求最小值：维护递增队列（队头最小）
• 求最大值：维护递减队列（队头最大）

入队时弹出破坏单调性的队尾元素；出队时弹出过期的队头元素。

关键数据结构

• F_队列_Queue — 单调队列 (deque) 实现滑动窗口最值
• A_容器_Container — vector 作为滑动窗口的底层数组

---

定长滑动窗口

窗口长度固定为 k，每次右移一格，只需要更新一个进入元素和一个离开元素。

// 求长度为 k 的连续子数组的最大和
#include <iostream>
using namespace std;
int a[100005];
 
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    int sum = 0, ans = -1e9;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (i >= k) sum -= a[i - k];
        if (i >= k - 1) ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

---

不定长滑动窗口

窗口两端均单调移动，常用于”满足条件的最短/最长区间”问题。

核心框架：

int l = 0;
for (int r = 0; r < n; r++) {
    加入 a[r] 到窗口;
    while (窗口不满足条件) {
        移除 a[l];
        l++;
    }
    更新答案;
}

---

P1886 滑动窗口 / 单调队列

题目: 有一个长为 n 的序列 a，以及一个大小为 k 的窗口。窗口从最左端滑到最右端，
每次输出窗口内的最小值和最大值。

思路: 用单调队列（deque）维护窗口最值，均摊 O(n)。

#include <iostream>
#include <deque>
using namespace std;
int a[1000005];
deque<int> q;
 
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    // 最小值：维护递增队列，队头最小
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] >= a[i])
            q.pop_back();
        q.push_back(i);
        if (q.front() <= i - k) q.pop_front();
        if (i >= k) cout << a[q.front()] << " ";
    }
    cout << endl;
    q.clear();
 
    // 最大值：维护递减队列，队头最大
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] <= a[i])
            q.pop_back();
        q.push_back(i);
        if (q.front() <= i - k) q.pop_front();
        if (i >= k) cout << a[q.front()] << " ";
    }
    return 0;
}

---

P2032 扫描

题目: 有一个 n 个数的数列，对于每个长度为 k 的连续区间，求出区间最大值。

思路: 同 P1886，单调队列维护滑动窗口最大值。

#include <iostream>
#include <deque>
using namespace std;
int a[2000005];
deque<int> dq;
 
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && a[dq.back()] <= a[i])
            dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k) cout << a[dq.front()] << endl;
    }
    return 0;
}

推荐练习题（洛谷）

• P1886 滑动窗口/单调队列

---

相关技巧

---

• 双指针: 滑动窗口是双指针的特化，区别在于窗口连续
• 前缀和: 定长窗口和可直接用前缀和 O(1) 求
• 差分: 窗口移动时可用差分维护区间操作
• 贪心: 部分滑动窗口问题需要贪心决定窗口扩展/收缩策略
• F_队列_Queue: 单调队列(deque)实现滑动窗口最值

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |