NC51001. Sliding Window
描述
| Window position | Minimum value | Maximum 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 |
输入描述
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
输出描述
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
示例1
输入:
8 3 1 3 -1 -3 5 3 6 7
输出:
-1 -3 -3 -3 3 3 3 3 5 5 6 7
C++14(g++5.4) 解法, 执行用时: 134ms, 内存消耗: 9600K, 提交时间: 2020-10-04 19:50:08
#include<bits/stdc++.h>
using namespace std;
int a[1000007],b[1000007];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
int l=0,r=0;
b[r++]=1;
if(k==1)cout<<a[1]<<' ';
for(int i=2;i<=n;i++){
if(r>l&&i-b[l]>=k)l++;
while(r>l&&a[b[r-1]]>=a[i])r--;
b[r++]=i;
if(i>=k)cout<<a[b[l]]<<' ';
}
cout<<endl;
l=r=0;
b[0]=1;
r++;
if(k==1)cout<<a[1]<<' ';
for(int i=2;i<=n;i++){
if(r>l&&i-b[l]>=k)l++;
while(r>l&&a[b[r-1]]<=a[i])r--;
b[r++]=i;
if(i>=k)cout<<a[b[l]]<<' ';
}
cout<<endl;
return 0;
}
C(clang11) 解法, 执行用时: 67ms, 内存消耗: 7032K, 提交时间: 2021-03-21 17:28:03
#include<stdio.h>
int a[1000005],b[1000005],c[1000005];
int main()
{
int n,k,l,r,i;
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)scanf("%d",&a[i]);
l=0;r=0;c[0]=0;
if(k==1)printf("%d ",a[0]);
for(i=1;i<n;i++){
if(i-c[l]>=k)
l++;
while(a[c[r]]>=a[i]&&r>=l)r--;
c[++r]=i;
if(i>=k-1)
printf("%d ",a[c[l]]);
}
printf("\n");
l=0;r=0;b[0]=0;
if(k==1)printf("%d ",a[0]);
for(i=1;i<n;i++){
if(i-b[l]>=k)
l++;
while(a[b[r]]<=a[i]&&r>=l)r--;
b[++r]=i;
if(i>=k-1)
printf("%d ",a[b[l]]);
}
}
C++(g++ 7.5.0) 解法, 执行用时: 161ms, 内存消耗: 7152K, 提交时间: 2023-08-03 15:41:15
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
int hh=0,tt=-1;
for(int i=0;i<n;i++){
if(hh<=tt&&q[hh]<i-k+1)hh++;
while(hh<=tt&&a[q[tt]]>=a[i])tt--;
q[++tt]=i;
if(i>=k-1)printf("%d ",a[q[hh]]);
}
puts("");
hh=0,tt=-1;
for(int i=0;i<n;i++){
if(hh<=tt&&q[hh]<i-k+1)hh++;
while(hh<=tt&&a[q[tt]]<=a[i])tt--;
q[++tt]=i;
if(i>=k-1)printf("%d ",a[q[hh]]);
}
puts("");
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 108ms, 内存消耗: 7236K, 提交时间: 2020-06-21 17:17:46
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],b[1000005];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",a+i);
int l=1,r=0;
for(int i=1;i<=n;++i){
while(l<=r&&a[i]<=a[b[r]])--r;
b[++r]=i;
if(i>=k){
while(b[l]<=i-k)++l;
printf("%d ",a[b[l]]);
}
}
puts(""),l=1,r=0;
for(int i=1;i<=n;++i){
while(l<=r&&a[i]>=a[b[r]])--r;
b[++r]=i;
if(i>=k){
while(b[l]<=i-k)++l;
printf("%d ",a[b[l]]);
}
}
}