Description
给一个长度为 N 的数组，一个长为 K 的滑动窗体从最左端移至最右端，你只能看到窗口中的 K 个数，每次窗体向右移动一位，如下图：
你的任务是找出窗体在各个位置时的最大值和最小值。
Input
Output
第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开；
第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。
Sample Input
83
13 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
33 5 5 6 7
参考程序
#include <stdio.h>
#define LEN 1000000
void GetMax_Min(int a[],int start,int end,int *max,int *min)
{
int i;
*max=a[start];
*min=a[start];
for(i=start+1;i<=end;i++)
{
if(a[i]>*max)
{
*max=a[i];
}
else
{
if(a[i]<*min)
{
*min=a[i];
}
}
}
}
void OutputList(int a[],int n)
{
int i;
for(i=0;i<n-1;i++)
{
printf("%d ",a[i]);
}
printf("%d\n",a[i]);
}
int main()
{
int N,K,a[LEN+5],i,j;
int maxList[LEN+5],minList[LEN+5],cnt=0;
scanf("%d%d",&N,&K);
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
int min,max;
GetMax_Min(a,0,K-1,&max,&min);
maxList[cnt]=max;
minList[cnt]=min;
cnt++;
for(i=1;i+K<=N;i++)
{
if(a[i-1]==min|| a[i-1]==max)
{
GetMax_Min(a,i,i+K-1,&max,&min);
}
else
{
if(a[i+K-1]>max)
{
max=a[i+K-1];
}
else
{
if(a[i+K-1]<min)
{
min=a[i+K-1];
}
}
}
maxList[cnt]=max;
minList[cnt]=min;
cnt++;
}
OutputList(minList,cnt);
OutputList(maxList,cnt);
return 0;
}
分析：
本题一个很自然的做法就是直接模拟，利用两层循环来解题。主函数如下（其余函数不需要修改）
int main()
{
int N,K,a[LEN+5],i;
int maxList[LEN+5],minList[LEN+5],cnt=0;
scanf("%d%d",&N,&K);
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
int min,max;
for(i=0;i+K<=N;i++)
{
GetMax_Min(a,i,i+K-1,&max,&min);
maxList[cnt]=max;
minList[cnt]=min;
cnt++;
}
OutputList(minList,cnt);
OutputList(maxList,cnt);
return 0;
}
但是这个算法是“不聪明的”，因为数据量会达到10^6，会运行超时。关键问题在于，两个相邻的滑动窗口在滑动的时候，里面绝大部分数据没变，只是滑动窗口的开头、结尾改变。滑动窗口移动的时候，类似于一个队列，队首出队一个数再从队尾入队一个数。所以只需关注出队、入队的元素即可。滑动窗口经过一次滑动后，如果出队的数恰好是上一步的最大（或者最小值），那么这时一定要基于整个滑动窗口重新扫描一遍，求出最大最小值，更新。但如果出队的元素既不是上一步的最大值也不是最小值，那么只需比较入队的元素会不会对滑动窗口内的最值造成影响即可，必要的话更新max，min值。这样减少了整个滑动窗口的扫描次数，一定程度上能提高效率，运用了动态规划的思想。
希望各位不吝赐教，提供更好地思路，共同进步~~
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: