题目链接

#10175. 「一本通 5.5 例 1」滑动窗口 - 题目 - LibreOJ (loj.ac)

前言

之前已经写过这道题的题解(2022GDUT寒假专题学习-1 B,F,I,J题 - blockche - 博客园 (cnblogs.com))，当时用的是 deque 模拟单调队列的方法来维护最大值，但后来突然发现其实可以直接用 priority_queue 优先队列来写，方便很多。

经过对比，两者的效率也是几乎一样的，但前者会快一点。

题目

给一个长度为 的数组，一个长为 的滑动窗体从最左端移至最右端，你只能看到窗口中的 个数，每次窗体向右移动一位，如下图：

你的任务是找出窗体在各个位置时的最大值和最小值。

思想

将每个数和下标依次压进 priority_queue , 此时队列头就是当前窗口的最大值 or 最小值。

每次比较当前 i 和队列头的下标，如果队列头已经出了滑动窗口，则删去，即i >= minn.top().second + k - 1时弹出队列头。

代码

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define SF ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f;
int main() {
    SF;
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    priority_queue<P> maxn;
    priority_queue<P, vector<P>, greater<P>> minn;
    vector<P> ans;
    maxn.push({a[0], 0}), minn.push({a[0], 0});
    for (int i = 1; i < n; ++i) {
        maxn.push({a[i], i}), minn.push({a[i], i});
        if (i + 1 >= k) {
            ans.push_back({minn.top().first, maxn.top().first});
            while (i >= minn.top().second + k - 1) minn.pop();
            while (i >= maxn.top().second + k - 1) maxn.pop();
        }
    }
    for (auto& x : ans) cout << x.first << ' ';
    cout << '\n';
    for (auto& x : ans) cout << x.second << ' ';
    return 0;
}