题目链接：

题意：给出一个n*m的矩阵。在所有K*K的子矩阵中，最大最小差值最小的是多少？

思路：枚举每一行，枚举每一列，（r,c），将（r-K+1,c-K+1）中的数字插入到单调队列中保存（这里设置两个单调队列，一个最大一个最小）。每次计算以（r,c）为右下角的子矩阵的值时，判断队列头元素的列数是不是大于等于c-K+1，否则删掉队头。插入时，比如维护最小的单调队列，要判断队尾的元素是不是小于当前元素，不小于则删掉队尾。

 

int n,m,K;

pair<int,int> Q1[N],Q2[N];

int head1,tail1,head2,tail2;

int c[N][N];

pair<int,int> get(int r1,int r2,int t)

{

    int Min=INF,Max=-INF,i;

    FOR(i,r1,r2)

    {

        Min=min(Min,c[i][t]);

        Max=max(Max,c[i][t]);

    }

    return MP(Min,Max);

}

int cal(int r)

{

    head1=tail1=head2=tail2=0;

    int i,x,y,ans=INF;

    pair<int,int> p;

    for(i=1;i<=m;i++)

    {

        p=get(r-K+1,r,i);

        x=p.first;

        y=p.second;

        while(head1<tail1&&Q1[tail1-1].second>=x) tail1--;

        Q1[tail1++]=MP(i,x);

        while(head2<tail2&&Q2[tail2-1].second<=y) tail2--;

        Q2[tail2++]=MP(i,y);

        if(i<K) continue;

        while(Q1[head1].first<i-K+1) head1++;

        x=Q1[head1].second;

        while(Q2[head2].first<i-K+1) head2++;

        y=Q2[head2].second;

        if(y-x<ans) ans=y-x;

    }

    return ans;

}

int main()

{

    RD(n,m,K);

    int i,j;

    FOR1(i,n) FOR1(j,m) RD(c[i][j]);

    int ans=INF,temp;

    for(i=K;i<=n;i++)

    {

        temp=cal(i);

        if(temp<ans) ans=temp;

    }

    PR(ans);

    return 0;

}