跳转至

滑动窗口

前置知识

双指针

目标

滑动窗口模板题

滑动窗口

双指针：以 r 为基础指针并根据题目要求来移动 l 或者保持 l 不动，同时 ans 由每一步的 r-l 来更新。

滑动窗口：以 l 为基础指针，并且 l~r 看做一个窗口，r 不断右移，根据题目要求来右移一次 l 或者保持 l 不动，特点是 r-l 始终不减，ans 为最终的 r-l。

区别：双指针算法当需要移动 l 指针时，可能移动多个单位以满足要求。而滑动窗口算法当需要移动 l 指针时，每次必定只移动一个单位！

https://codeforces.com/problemset/problem/1955/D

a数组中所有长度为m的子串，和b数组中的元素对比，至少有k个是相同的

看窗口内相同的元素的个数，是否>=k

#include <bits/stdc++.h>

using namespace std;

int T, n, m, k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        vector<int> a(n), b(m);

        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < m; i++) cin >> b[i];

        map<int, int> cnta, cntb;
        for (int i = 0; i < m; i++) cntb[b[i]]++;

        int cnt = 0, ret = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (i - j + 1 > m) {
                cnta[a[j]]--;
                if (cnta[a[j]] < cntb[a[j]]) cnt--;
                j++;
            }

            if (cnta[a[i]] < cntb[a[i]]) cnt++;
            cnta[a[i]]++;

            if (i >= m - 1 && cnt >= k) {
                ret++;
            }
        }

        cout << ret << '\n';
    }

    return 0;
}

POJ2823 Sliding Window

// 结合了单调队列
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;

int a[N], q[N], n, k;
int hh, tt;

int main(){
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++){
        // 窗口滑出去了
        if (hh <= tt && i - k + 1 > q[hh]) hh++; 

        // 较小的值入队
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;

        q[++tt] = i;

        // 窗口是满的就输出,没满k宽度的时候，是不可输出的
        // 队列是单调递增的，队头是窗口里的最小值
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++){
        // 窗口滑出去了
        if (hh <= tt && i - k + 1 > q[hh]) hh++; 

        // 较小的值入队
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;

        q[++tt] = i;

        // 窗口是满的就输出,没满k宽度的时候，是不可输出的
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    puts("");


    return 0;
}

参考

  • https://blog.csdn.net/lyqptp233/article/details/113774583 算法系列--滑动窗口与双指针
  • https://www.acwing.com/solution/content/240594/