单调队列
传送门
模板题，背过即可
题目
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
样例
输入#1
8 3
1 3 -1 -3 5 3 6 7
输出#1
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据范围
1 ≤ N ≤ 105
1 ≤ a [ i ] ≤ 109
实现代码
数组模拟， q [ ] 存 下 标
#include <iostream> #include <queue> using namespace std; const int N = 1000010; int n, k, a[N]; int q[N], hh, tt = -1; int main() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) { while(hh <= tt && i - k + 1 > q[hh]) hh++; while(hh <= tt && a[q[tt]] >= a[i]) tt--; q[++tt] = i; if(i + 1 >= k) cout << a[q[hh]] << ' '; } cout << endl; hh = 0, tt = -1; for (int i = 0; i < n; i++) { while(hh <= tt && i - k + 1 > q[hh]) hh++; while(hh <= tt && a[q[tt]] <= a[i]) tt--; q[++tt] = i; if(i + 1 >= k) cout << a[q[hh]] << ' '; } return 0; }
deque
#include <iostream> #include <queue> using namespace std; const int N = 1000010; deque<int> q; int n, k, a[N]; int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { while(!q.empty() && i - q.front() + 1 > k) q.pop_front(); while(!q.empty() && a[q.back()] >= a[i]) q.pop_back(); q.push_back(i); if(i >= k) cout << a[q.front()] << ' '; } cout << endl; q = deque<int>(); for (int i = 1; i <= n; i++) { while(!q.empty() && i - q.front() + 1 > k) q.pop_front(); while(!q.empty() && a[q.back()] <= a[i]) q.pop_back(); q.push_back(i); if(i >= k) cout << a[q.front()] << ' '; } return 0; }
