2513 - 滑动窗口
给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：
|
Window position |
Min value |
Max value |
|
[ 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 |
数据范围：
20%： n<=500; 50%: n<=100000;
100%: n<=1000000;
Input
第1行nk第2行为长度为n的数组
Output
2行，第1行每个位置的min value第2行每个位置的max value
Examples
Input
8 3 1 3 -1 -3 5 3 6 7
Output
-1 -3 -3 -3 3 3 3 3 5 5 6 7
Solution C++
#include<iostream> #include<cstdio> #include<cstring> #include<deque> using namespace std; deque<int> q_max,q_min; int n,k,a[1000001]; int b[1000001],c[1000001]; void insert(int,bool); void init(); void work(); int main() { //freopen("window6.in","r",stdin); //freopen("window.out","w",stdout); init(); work(); return 0; } void init() { cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; } void work() { for(int i=1;i<k;i++) { insert(i,0); insert(i,1); } for(int i=k;i<=n;i++) { insert(i,0); insert(i,1); while(!q_max.empty()&&q_max.front()<i-k+1) q_max.pop_front(); while(!q_min.empty()&&q_min.front()<i-k+1) q_min.pop_front(); b[i]=a[q_max.front()]; c[i]=a[q_min.front()]; } for(int i=k;i<n;i++) cout<<c[i]<<' ';cout<<c[n]<<endl; for(int i=k;i<n;i++) cout<<b[i]<<' ';cout<<b[n]<<endl; } void insert(int x,bool f) { if(f) { while(!q_max.empty() && a[q_max.back()]<=a[x]) q_max.pop_back(); q_max.push_back(x); } else { while(!q_min.empty() && a[q_min.back()]>=a[x]) q_min.pop_back(); q_min.push_back(x); } }