简答题
偏难
#7217
滑动窗口 给定一个长度为n(n<=10^6)的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距…
滑动窗口
给定一个长度为n(n<=10^6)的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子:
数组是 [1 3 -1 -3 5 3 6 7], k = 3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是得到滑动窗口在每个位置时的最大值和最小值。
时间限制:20000
内存限制:65536
输入
输入包括两行。 第一行包括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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N], q[N];
int n, k;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
// 最小值队列 建立单调递增队列
int h = 0, t = -1;
for (int i = 1; i <= n; i++) {
if (t >= h && q[h] < i - k + 1)
h++;
while (t >= h && a[i] <= a[q[t]])
t--;
q[++t] = i;
if (i >= k)
printf("%d ", a[q[h]]);
}
printf("\n");
// 最大值队列 建立单调递减队列
h = 0, t = -1;
for (int i = 1; i <= n; i++) {
// 队列中有元素且队头元素不在窗口[i-m+1,i]内,队头出队
if (h <= t && q[h] < i - k + 1)
h++;
// 队列中有元素且当前值>=队尾值,队尾出队
while (h <= t && a[i] >= a[q[t]])
t--;
// 下标入队,便于队头出队
q[++t] = i;
// 使用队头最大值
if (i >= k)
printf("%d ", a[q[h]]);
}
return 0;
}</pre>
这道题暂未补解析。