洛谷P2216 HAOI2007 理想的正方形 （单调队列）

题目就是要求在n*m的矩形中找出一个k*k的正方形（理想正方形），使得这个正方形内最值之差最小（就是要维护最大值和最小值），显然我们可以用单调队列维护。

但是二维平面上单调队列怎么用？

我们先对行处理，将其压缩为一个（n-k+1）*m的矩形；再对列进行处理，最终压缩为一个（n-k+1）*（m-k+1）的矩形，枚举最大与最小之差，更新答案即可。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=1e3+1;

 4 int n,m,k,a[N][N],ans;

 5 int qmax[N],qmin[N],h1,t1,h2,t2;

 6 int Max1[N][N],Min1[N][N],Max2[N][N],Min2[N][N];

 7 int main(){

 8     scanf("%d%d%d",&n,&m,&k);

 9     for(int i=1;i<=n;i++)

10         for(int j=1;j<=m;j++)

11             scanf("%d",&a[i][j]);

12

13     for(int i=1;i<=n;i++){

14         h1=1,t1=0,h2=1,t2=0;

15         qmax[++t1]=1;qmin[++t2]=1;

16         for(int j=2;j<=m;j++){

17             while(h1<=t1 && a[i][j]>=a[i][qmax[t1]]) t1--;

18             qmax[++t1]=j;

19             while(h2<=t2 && a[i][j]<=a[i][qmin[t2]]) t2--;

20             qmin[++t2]=j;

21             while(h1<=t1 && qmax[h1]<j-k+1) h1++;

22             while(h2<=t2 && qmin[h2]<j-k+1) h2++;

23             if(j>=k){

24                 Max1[i][j-k+1]=a[i][qmax[h1]];

25                 Min1[i][j-k+1]=a[i][qmin[h2]];

26             }

27         }

28     }

29

30     for(int j=1;j<=m-k+1;j++){

31         h1=1,t1=0,h2=1,t2=0;

32         qmax[++t1]=1;qmin[++t2]=1;

33         for(int i=2;i<=n;i++){

34             while(h1<=t1 && Max1[i][j]>=Max1[qmax[t1]][j]) t1--;

35             qmax[++t1]=i;

36             while(h2<=t2 && Min1[i][j]<=Min1[qmin[t2]][j]) t2--;

37             qmin[++t2]=i;

38             while(h1<=t1 && qmax[h1]<i-k+1) h1++;

39             while(h2<=t2 && qmin[h2]<i-k+1) h2++;

40             if(i>=k){

41                 Max2[i-k+1][j]=Max1[qmax[h1]][j];

42                 Min2[i-k+1][j]=Min1[qmin[h2]][j];

43             }

44

45         }

46     }

47     ans=0x3f3f3f3f;

48     for(int i=1;i<=n-k+1;i++)

49         for(int j=1;j<=m-k+1;j++)

50             ans=min(ans,Max2[i][j]-Min2[i][j]);

51     cout<<ans;

52 }    

用了不知多少次的单调队列，最终压缩的矩形中每个格子代表的意义是：以它为右下角的n*n的正方形。

洛谷P2216 HAOI2007 理想的正方形 （单调队列）的相关教程结束。