跳转至

刷题总结

滑动窗口

单向队列queue,#include <queue> , 仅支持插入队尾push(int i),弹出队头pop()

双向队列duque,#include<deque>, 支持插入队头push_front(int i),插入队尾push_back(int i),删除队头pop_front(),删除队尾pop_back()

对于一般的滑动窗口,如果不用pop队尾,可以用queue

        queue<int> q;
        // 遍历序列每个元素
        for(int i = 0; i < n; i++){
        // 检查新加入的元素是否满足条件,如果满足,加入队尾
        if(check(q.front(), i))
                q.push(i);
        // 根据问题,对插入的nums[i]操作
        ...
        // check(q.front())意为:检查队头是否满足条件,如果不满足,则弹出
                while(!q.empty() && check(q.front())){
                        q.pop();
                }
        }

如果需要求滑动窗口最大最小值,可以使用deque

        deque<int> q;
        // 遍历序列每个元素
        for(int i = 0; i < n; i++){
        // 检查队头是否满足条件,如果不满足,弹出队头    
        while(!q.empty() && check(q.front()))   q.pop_front();
        // 检查队尾是否满足条件,如果不满足,弹出队尾
        while(!q.empty() && check(q.back(), i)) q.pop_back(i);
        // 将新元素加入队尾
        q.push_back(i);
        }

例如acwing 154 滑动窗口

https://www.acwing.com/problem/content/156/

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

const int N = 1e6 + 10;
int a[N];
int n, k;

int main(){
    deque<int> q;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    // 求滑动窗口最小值
    for(int i = 0; i < n; i++){
        // 队列存储的是滑动窗口的最小值的索引
        // 队列的长度不一定为k

        // 窗口第一个元素的索引为idx,长度为k的窗口对应的末尾元素的索引为idx + k - 1,也为i
        // 所以i = idx + k - 1 或idx = i - k + 1
        // 可推出:
        // (1)i = idx + k - 1:
        //      所以一开始idx = 0,窗口未满,往里面填元素,当i == k - 1时,窗口刚好满;之后i > k - 1
        // (2)idx = i + k - 1:
        //      想要保持窗口一直为k,那么需要idx = i - k + 1 <= q.front()
        //      如果i - k + 1 > q.front() 说明队头已经不在窗口内,需要弹出


        // pop前保证队列不为空 且 保证窗口始终保持在k个
        // 如果超出k个,说明队头需要弹出
        // 如果不足或等于k个,队头也不需要弹出
        while(!q.empty() && i - k + 1 > q.front()) q.pop_front();
        // pop前保证队列不为空 且 如果队尾元素a[q.back()]比新元素a[i]还小
        // 那么只要a[i]还在窗口内,之后窗口的最小值一定不为a[q.back()]
        // 因此弹出队尾元素
        while(!q.empty() && a[i] < a[q.back()]) q.pop_back();
        q.push_back(i);

        if(i - k + 1 >= 0)
            cout << a[q.front()] << " ";
    }
    q.clear();
    cout << endl;
    // 求滑动窗口最大值
    for(int i = 0; i < n; i++){
        while(!q.empty() && i - q.front() + 1 > k) q.pop_front();
        while(!q.empty() && a[i] > a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i - k + 1 >= 0)
            cout << a[q.front()] << " ";
    }
}

当然,还可以使用双指针,只需要指向原来的数组即可

图:网格问题

网格问题

并查集

可解决图的连通分量问题

单调栈