[Leaf] [P2216] 理想的正方形

p2216-[haoi2007]-理想的正方形---洛谷">P2216 [HAOI2007] 理想的正方形 - 洛谷

1. 题面梗概

中译中：有一个 $a \times b$ 的整数组成的矩阵，现请从中找出一个 $n \times n$ 的小正方形，使得该区域内的最大值和最小值的差最小。

$2 \leq a, b \leq 10^3, n \leq a, n \leq b, n \leq 100$

2. 逻辑推导

稍一转换就发现，这其实就是二维版的滑动窗口最值问题，但麻烦也麻烦在这，这是二维的。

2.1 建模

一个二维的正方形窗口，其实可以拆解成“行”和“列”的组合。

1. 第一步：行向压缩。

   • 我们先对每一行单独处理。用单调队列求出每一行中，所有长度为 $n$ 的区间的最大值和最小值。
   • 这时候，原本的 $A \times B$ 矩阵变成了两个新矩阵：row_max[i][j] 和 row_min[i][j]。这里的 $(i, j)$ 代表第 $i$ 行中以 $j$ 为结尾的长度为 $n$ 的段。

2. 第二步：列向折叠。

   • 现在我们手里有每一行的小段最值了。接下来，我们对着这些新矩阵的每一列再跑一遍单调队列（窗口大小也是 $n$）。
   • 然后我们就获得了 $n \times n$ 矩阵的两个最值。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 50;

int a, b, n;
int mat[maxn][maxn];

int rmin[maxn][maxn];
int rmax[maxn][maxn];

int amin[maxn][maxn];
int amax[maxn][maxn];

int main()
{	
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> a >> b >> n;

    for( int i = 1; i <= a; ++ i )
    {
        for( int j = 1; j <= b; ++ j )
        {
            cin >> mat[i][j];
        }
    }

    for( int i = 1; i <= a; ++ i )
    {
        deque<int> qmin, qmax;
        for( int j = 1; j <= b; ++ j )
        {
            while( !qmin.empty( ) && mat[i][qmin.back( )] >= mat[i][j] )
                qmin.pop_back( );
            qmin.push_back( j );
            while( !qmin.empty( ) && qmin.front( ) <= j - n )
                qmin.pop_front( );
            
            while( !qmax.empty( ) && mat[i][qmax.back( )] <= mat[i][j] )
                qmax.pop_back( );
            qmax.push_back( j );
            while( !qmax.empty( ) && qmax.front( ) <= j - n )
                qmax.pop_front( );
            
            if( j >= n )
            {
                rmin[i][j - n + 1] = mat[i][ qmin.front( ) ];
                rmax[i][j - n + 1] = mat[i][ qmax.front( ) ];
            }
        }
    }

    for( int j = 1; j <= b - n + 1; ++ j )
    {
        deque<int> qmin, qmax;
        for( int i = 1; i <= a; ++ i )
        {
            while( !qmin.empty( ) && rmin[qmin.back( )][j] >= rmin[i][j] )
                qmin.pop_back( );
            qmin.push_back( i );
            while( !qmin.empty( ) && qmin.front( ) <= i - n )
                qmin.pop_front( );
            
            while( !qmax.empty( ) && rmax[qmax.back( )][j] <= rmax[i][j] )
                qmax.pop_back( );
            qmax.push_back( i );
            while( !qmax.empty( ) && qmax.front( ) <= i - n )
                qmax.pop_front( );
            
            if( i >= n )
            {
                amin[i - n + 1][j] = rmin[ qmin.front( ) ][j];
                amax[i - n + 1][j] = rmax[ qmax.front( ) ][j];
            }
        }
    }

    int ans = 1e9;
    for( int i = 1; i <= a - n + 1; ++ i )
    {
        for( int j = 1; j <= b - n + 1; ++ j )
        {
            ans = min( ans, amax[i][j] - amin[i][j] );
        }
    }

    cout << ans << '\n';
    return 0;
}

4. 复盘

• 复杂度: $O( ab )$。

• 碎碎念: 这种 先行后列 的降维思想在处理矩阵区域最值的时候很有用。

• 关联笔记: 单调队列