题目详情

小蓝有一个序列a[1], a[2]. .... a[n]. 给定一个正整数k，请问对于每一个1到n之间的序号i，a[i-k], a[i-k+1].... a[i+k]这2k+1个数中的最小值是多少?当某个下标超过1到n的范围时，数不存在，求最小值时只取存在的那些值。

输入格式

输入的第一行包含一整数n。 第二行包含n个整数，分别表示a[1], a[2]. ... a[n]。第三行包含一个整数k。

输出格式

输出一行，包含n个整数，分别表示对于每个序号求得的最小值。

样例输入

5
5 2 7 4 3
1

样例输出

2 2 2 3 3

  • 对于30%的评测用例，1<= n<= 1000，1 <= a[i]<=1000。
  • 对于50%的评测用例，1<= n<= 10000，1 <= a[]<=10000。
  • 对于所有评测用例，1<= n<= 1000000，1 <= a[i]<=100000。
思路

由题意可知此题考察的是滑动窗口的最小值队列，窗口大小是2k+1，但在第一个位置和最后一个位置的时候，窗口大小不满足2k+1，我们可以在数组的前后各补k个数值大小为INT_MAX或0x7fffffff的数组元素。

代码部分

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,INF=0x7fffffff;
int a[N];
deque<int> q;
int main ()
{
	int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int k;scanf("%d",&k);
    for(int i=n;i>=1;i--) a[i+k]=a[i];//给数组前边留k个位置
    for(int i=1;i<=k;i++)
    {
    	a[i]=INF;// 前k个位置赋值
        a[n+k+i]=INF;// 后k个位置赋值
    }
    n=n+2*k;
    k=2*k+1;
    for(int i=1;i<=n;i++)
    {
		while(!q.empty()&&i-k>=q.front()) q.pop_front();
        while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k) printf("%d ",a[q.front()]);
    }
    return 0;
}