|
题目：
有一堆数字共N个数字，以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
题解：
用单调队列，判断完依次输出队头。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 1;
int a[N];
int main() {
? ? int n, k;
? ? cin >> n >> k;
? ? int m;
? ? vector<int>v;//单调递减队列
? ? for (int i = 0; i < n; ++i) {
? ? ? ? cin >> m;
? ? ? ? v.push_back(m);
? ? }
? ? vector<int> v_MAX, v_MIN,
? ? ? ? q(v.size(), 0);//放下标
? ? int x = 0, y = -1;
? ? for (int i = 0; i < (int)v.size(); ++i) {
? ? ? ? while (x <= y && v[q[y]] > v[i]) {
? ? ? ? ? ? --y;
? ? ? ? }
? ? ? ? q[++y] = i;
? ? ? ? if (i - q[x] + 1 > k) ?++x;
? ? ? ? if (i >= k - 1) v_MIN.push_back(v[q[x]]);
? ? }
? ? for (int i = 0; i < (int)v_MIN.size(); ++i)
? ? ? ? printf("%d"" ", v_MIN[i]);
? ? printf("\n");
? ? q.clear();
? ? int l = 0, r = -1;
? ? for (int i = 0; i < (int)v.size(); ++i) {
? ? ? ? while (l <= r && v[q[r]] < v[i]) {
? ? ? ? ? ? --r;
? ? ? ? }
? ? ? ? q[++r] = i;
? ? ? ? if (i - q[l] + 1 > k) ?++l;
? ? ? ? if (i >= k - 1) v_MAX.push_back(v[q[l]]);
? ? }
? ? for (int i = 0; i < (int)v_MAX.size(); ++i)
? ? ? ? printf("%d"" ", v_MAX[i]);
? ? return 0;
}
|