当前位置:网站首页>AcWing 1091. 理想的正方形 (求两次单调队列 )

AcWing 1091. 理想的正方形 (求两次单调队列 )

2021-03-08 12:36:29 glm233

这道题我们可以将每一行的滑动窗口求出来 然后统一放在窗口的最后一个位置 最后进行列的滑动窗口压缩 最大值最小值分别做一次 遍历一遍预处理出的最大值和最小值数组 更新答案即可

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k,a[N][N],ans_min[N][N],ans_max[N][N];
void getmin(int a[],int b[],int n){
    deque<int>q;
    for(int i=1;i<=n;i++){
        if(!q.empty()&&i-q.front()>=k)q.pop_front();
        while(!q.empty()&&a[q.back()]>=a[i])q.pop_back();
        q.push_back(i);
        b[i]=a[q.front()];
    }
}
void getmax(int a[],int b[],int n){
    deque<int>q;
    for(int i=1;i<=n;i++){
        if(!q.empty()&&i-q.front()>=k)q.pop_front();
        while(!q.empty()&&a[q.back()]<=a[i])q.pop_back();
        q.push_back(i);
        b[i]=a[q.front()];
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=n;i++){
        getmin(a[i],ans_min[i],m),getmax(a[i],ans_max[i],m);
        /*for(int j=1;j<=m;j++){
            cout<<ans_min[i][j]<<" ";
        }
        cout<<endl;*/
    }
    int ans=INT_MAX,tepa[N],tarb[N],tarc[N];
    for(int i=k;i<=m;i++){
        for(int j=1;j<=n;j++){
            tepa[j]=ans_min[j][i];
        }
        getmin(tepa,tarb,n);
        for(int j=1;j<=n;j++){
            tepa[j]=ans_max[j][i];
        }
        getmax(tepa,tarc,n);
        for(int j=k;j<=n;j++)ans=min(ans,tarc[j]-tarb[j]);
    }
    cout<<ans<<endl;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

版权声明
本文为[glm233]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1798536