总时间限制: 12000ms
内存限制: 65536kB
描述
给定一个长度为n（n<=10^6）的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子：
数组是 [1 3 -1 -3 5 3 6 7]， k = 3。
窗口位置最小值最大值[1 3 -1] -3 5 3 6 7 -13 1 [3 -1 -3] 5 3 6 7 -33 1 3 [-1 -3 5] 3 6 7 -35 1 3 -1 [-3 5 3] 6 7 -35 1 3 -1 -3 [5 3 6] 7 36 1 3 -1 -3 5 [3 6 7]37
你的任务是得到滑动窗口在每个位置时的最大值和最小值。
输入
输入包括两行。 第一行包括n和k，分别表示数组的长度和窗口的大小。 第二行包括n个数字。
输出
输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。
样例输入
8 3 1 3 -1 -3 5 3 6 7样例输出
-1 -3 -3 -3 3 3 3 3 5 5 6 7 #include <iostream> #include <cstring> #include <algorithm> #include <climits> #include <deque> using namespace std; const int MAXN = 1e6; int n, k; int a[MAXN+5]; int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); /* min */ deque<int> q; for (int i = 0; i < k-1; ++i) { while (!q.empty() && a[q.front()] > a[i]) q.pop_front(); q.push_front(i); } for (int i = k-1; i < n; ++i) { if (!q.empty() && i - q.back() >= k) q.pop_back(); while (!q.empty() && a[q.front()] > a[i]) q.pop_front(); q.push_front(i); printf("%d ", a[q.back()]); } printf("\n"); /* max */ q.clear(); for (int i = 0; i < k-1; ++i) { while (!q.empty() && a[q.front()] < a[i]) q.pop_front(); q.push_front(i); } for (int i = k-1; i < n; ++i) { if (!q.empty() && i - q.back() >= k) q.pop_back(); while (!q.empty() && a[q.front()] < a[i]) q.pop_front(); q.push_front(i); printf("%d ", a[q.back()]); } printf("\n"); system("pause"); return 0; }【分析】
单调队列问题，十分巧妙
可以看看这篇题解
