C++ :

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1e6+5;
int a[maxn],q[maxn];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k,hh=0,tt=-1;//队头指针hh，队尾指针tt
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i-k+1>0) cout<<" ";//因为格式化输出空格，i-k+1为当前窗口第一个元素下标
        if(hh<=tt&&q[hh]<i-k+1) hh++;//如果队头元素保存的下标比当前窗口第一个元素下标小，说明当前队头元素不在当前窗口内，就要删去（队头元素的下标不一定是每次窗口最左边的那个（有可能那个已经被删掉了），所以队列中要保存下标，根据下标来做这个判断）
        while(hh<=tt&&a[q[tt]]>a[i]) tt--;//只要当前队尾元素对应的数值比当前数大，则删去队列中当前的对尾元素，保证队列的单调递增，这里的循环不会造成超时，因为考虑最坏情况，每隔k个数才会遇见一个当前数比队列中所有元素都小，这样整个题的时间复杂度就为o（n/k*k）=o(n);
        q[++tt]=i;//然后每次把当前数的下标插入到队列尾
        if(i-k+1>=0) cout<<a[q[hh]];//这样每次o(1)地输出队头元素对应的数值即为当前窗口最小值
    }
    cout<<endl;
    //接下来，求最大值同上，让单调队列保证递减即可
    memset(q,0,sizeof q);
    hh=0,tt=-1;
    for(int i=0;i<n;i++){
        if(i-k+1>0) cout<<" ";
        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>=0) cout<<a[q[hh]];
    }
    return 0;
}

这道题大意就是让我们求区间内的最大最小值，就是一道RMQ问题，可以用单调队列解决。

单调队列，顾名思义就是一个所有元素都有单调性的队列，我们可以建立一个队列来维护这些数据。

首先每加入新元素前，我们要检查队首是否还在需统计的区间中，若否，出队。

其次，维护队列单调性。以区间最大值为例，如果当前元素比队尾元素大，就不停出队，直到元素不大于队尾元素为止。

处理完后，区间的最大值就是队首元素，直接输出即可。

以下为部分代码，为防止复制就没全贴上来了（笑）：

//区间最小值
for(int i=1;i<=n;i++){
		while(!q.empty()&&i-k>=q.front()){
			q.pop_front();
		}//检查队首是否还在需统计的区间中
		while(!q.empty()&&a[i]<=a[q.back()]){
			q.pop_back();
		}//维护队列单调性
		q.push_back(i);
		if(i>=k){
			cout<<a[q.front()]<<" ";
		}//输出
	}
	cout<<endl;
	q.clear();//一定要清空，因为你接下来还有算区间最大值

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,m;
int q1[1000001],q2[1000001];
int a[1000001];
int min_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q1[h]+m<=i) h++;
        while(h<=t&&a[i]<a[q1[t]]) t--;
        q1[++t]=i;
        if(i>=m) printf("%d ",a[q1[h]]);
    }
    cout<<endl;
}
int max_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q2[h]+m<=i) h++;
        while(h<=t&&a[i]>a[q2[t]]) t--;
        q2[++t]=i;
        if(i>=m) printf("%d ",a[q2[h]]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    min_deque();
    max_deque();
    return 0;
}

#include #include<stdio.h> #include #include #include

using namespace std;

const int N=1e7+100; int q[N],a[N];

int main() { int n,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; int l,r; l=r=1; for(int i=1;i<=n;i++) { while(l<r&&a[q[r-1]]>=a[i]) { r--; } q[r++]=i; if(i-q[l]>=k) l++; if(i>=k) cout<<a[q[l]]<<" "; } cout<<endl; l=r=1; for(int i=1;i<=n;i++) { while(l<r&&a[q[r-1]]<=a[i]) { r--; } q[r++]=i; if(i-q[l]>=k) l++; if(i>=k) cout<<a[q[l]]<<" "; } return 0; }

给爷点赞！！！！（已防复制）

#include<iostream> 
#include<cstring>
using namespace sd; 
int n, a, l, r；
int arr[1000005], q[1000005];
int main(){
	cin >> n >> a;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    for(int i = 1; i <= n; i++){
        int temp = arr[i];
        while(r > l && arr[q[r-1]] >= temp)
            r--;
        q[r++] = i;
        if(i - q[l] >= a)   l++;
        if(i >= a)
            cout << arr[q[l]] << ' ';
    }
    cout << endl;
    l = r = 0;
    for(int i = 1; i <= n; i++){
        int temp = arr[i];
        while(r > l && arr[q[r-1]] <= temp)
            r--;
        q[r++] = i;
        if(i - q[l] >= a)   l++;
        if(i >= a)
            cout << arr[q[l]] << ' ':
    }
    return 0;
}