理想的正方形

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1976 字
a×b矩阵中找n×n正方形，使其内部最大值与
一本通
练习
正文

/*
原题：T1604 「一本通 5.5 练习 3」理想的正方形
题意：a×b 矩阵中找 n×n 正方形，使其内部最大值与最小值之差最小，输出该最小差值。
思路：先用单调队列对每行做宽度为 n 的滑动窗口，得到每行各列的横向最大/最小值；
     再对每列做高度为 n 的滑动窗口，得到每个 n×n 块的纵向最大/最小值；差值取最小。
复杂度：时间 O(a·b)，空间 O(a·b)。
易错点：二维需先做行再做列；窗口大小 n 可能等于 1；矩阵元素与差值用 int 足够。
*/
#include <bits/stdc++.h>
using namespace std;
// 对一维数组 a 做窗口宽 w 的最大/最小，结果写入 mx/mn
void slide1d(const vector<int>& a,int w,vector<int>& mx,vector<int>& mn){
    int len=(int)a.size();
    deque<int> qmax,qmin;
    for(int i=0;i<len;i++){
        while(!qmax.empty()&&qmax.front()<=i-w){
            qmax.pop_front();
        }
        while(!qmin.empty()&&qmin.front()<=i-w){
            qmin.pop_front();
        }
        while(!qmax.empty()&&a[qmax.back()]<=a[i]){
            qmax.pop_back();
        }
        while(!qmin.empty()&&a[qmin.back()]>=a[i]){
            qmin.pop_back();
        }
        qmax.push_back(i);
        qmin.push_back(i);
        if(i>=w-1){
            mx.push_back(a[qmax.front()]);
            mn.push_back(a[qmin.front()]);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,n;
    cin>>a>>b>>n;
    vector<vector<int>> mat(a,vector<int>(b));
    for(int i=0;i<a;i++){
        for(int j=0;j<b;j++){
            cin>>mat[i][j];
        }
    }
    int cols=b-n+1;
    vector<vector<int>> rowMax(a,vector<int>(cols)),rowMin(a,vector<int>(cols));
    for(int i=0;i<a;i++){
        vector<int> mx,mn;
        slide1d(mat[i],n,mx,mn);
        rowMax[i]=mx;
        rowMin[i]=mn;
    }
    int rows=a-n+1;
    int ans=INT_MAX;
    for(int j=0;j<cols;j++){
        vector<int> vmax(a),vmin(a);
        for(int i=0;i<a;i++){
            vmax[i]=rowMax[i][j];
            vmin[i]=rowMin[i][j];
        }
        vector<int> cmx,cmn;
        slide1d(vmax,n,cmx,cmn);
        vector<int> cminv,sminv;
        slide1d(vmin,n,cminv,sminv);
        for(int i=0;i<rows;i++){
            ans=min(ans,cmx[i]-sminv[i]);
        }
    }
    cout<<ans<<'\n';
    return 0;
}
理想的正方形

正文

一本通·提高篇的其它内容
