题解：AT_awc0001_e 気温の変動幅

· · 题解

1. 题目思路

首先观察到，题目里所求值的区间长度是固定的，因此很容易想到单调队列，这道题就是单调队列的模板题目。

考虑对所求的最大值、最小值使用两个单调队列分开来求，然后将对应区间的最大值和最小值相减，取最大值即可。

2. 代码

注：代码仅供参考。

#include<bits/stdc++.h>
using namespace std;
const int max_n=2e5+2;
int n,k,a[max_n];
int q[max_n],hd,tl,max_[max_n],min_[max_n],ans;
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    hd=1; //队列头
    for(int i=1;i<=n;i++){
        while(hd<=tl&&a[q[tl]]<=a[i]){ //去掉无用值
            tl--;   
        }
        tl++;
        q[tl]=i; //加入队列末尾
        while(hd<=tl&&q[hd]<=i-k){ //去掉窗口外的值
            hd++;
        }
        if(i>=k){ //从 k 开始记录（之前的位置还不够一个区间）
            max_[i]=a[q[hd]];
        }
    }
    hd=1,tl=0; //重置，计算最小值
    for(int i=1;i<=n;i++){
        while(hd<=tl&&a[q[tl]]>=a[i]){
            tl--;   
        }
        tl++;
        q[tl]=i;
        while(hd<=tl&&q[hd]<=i-k){
            hd++;
        }
        if(i>=k){
            min_[i]=a[q[hd]];
        }
    }
    for(int i=k;i<=n;i++){ //计算答案
        ans=max(ans,max_[i]-min_[i]);
    }
    printf("%d\n",ans);
    return 0;
}

3. 后记

更多内容，请移步至：

  1. \color{red}\texttt{Luogu ryf2011}；
  2. \color{orange}\texttt{cnblogs（博客园） cnblogs2011ryf}。