滑动窗口——优先队列写法

P1886 滑动窗口 /【模板】单调队列 思路：

记录两个元素分别是元素值，元素下标。

因为元素下标不会过期， 所以可以用STL优先队列（priority_queue）。

分为一个升序的优先队列，降序的优先队列，每次看队首如果过期了就删掉，否则答案就是队首。

优先队列传送门

【原创】优先队列 priority_queue 详解-CSDN博客

代码： #include <bits/stdc++.h> using namespace std; struct Windows{ int x, id; bool operator < (const Windows &T) const { return x < T.x; } bool operator > (const Windows &T) const { return x > T.x; } }; int main() { ios::sync_with_stdio(false), cin.tie(0); int n, k; cin >> n >> k; priority_queue<Windows> Q; // 最大 priority_queue<Windows, vector<Windows>, greater<Windows>> Qless; // 最小 vector<Windows> A(n); for (int i = 0; i < n; i++) cin >> A[i].x, A[i].id = i; for (int i = 0; i < n; i++) { Qless.push(A[i]); while(Qless.top().id <= i - k) Qless.pop(); // 过期 if (i >= k - 1) cout << Qless.top().x << ' '; } cout << '\n'; for (int i = 0; i < n; i++) { Q.push(A[i]); while(Q.top().id <= i - k) Q.pop(); // 过期 if (i >= k - 1) cout << Q.top().x << ' '; } return 0; }