算法分析

单调队列

• 1、预处理出每一行i以j结尾且长度是k的滑动窗口的最小值和最大值，分别记录在row_min[i][j]，和row_max[i][j]位置中
• 2、在row_min[][] 和 row_max[][]中每一列再用滑动窗口求出最小值和最大值，表示的以i，j结尾且是长度是k的区域的最小值和最大值

时间复杂度 $O(nm)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static int INF = 0x3f3f3f3f;
    static int n,m,k;
    static int[][] w = new int[N][N];
    static int[][] row_min = new int[N][N];
    static int[][] row_max = new int[N][N];
    static int[] q = new int[N];
    static void get_min(int[] a,int[] b,int c)
    {
        int hh = 0,tt = -1;
        for(int i = 1;i <= c;i ++)
        {
            if(hh <= tt && q[hh] < i - k + 1) hh ++;
            while(hh <= tt && a[q[tt]] >= a[i]) tt --;
            q[++ tt] = i;
            b[i] = a[q[hh]];
        }
    }
    static void get_max(int[] a,int[] b,int c)
    {
        int hh = 0,tt = -1;
        for(int i = 1;i <= c;i ++)
        {
            if(hh <= tt && q[hh] < i - k + 1) hh ++;
            while(hh <= tt && a[q[tt]] <= a[i]) tt --;
            q[++ tt] = i;
            b[i] = a[q[hh]];
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        k = Integer.parseInt(s1[2]);
        for(int i = 1;i <= n;i ++)
        {
            String[] s2 = br.readLine().split(" ");
            for(int j = 1;j <= m;j ++)
            {
                w[i][j] = Integer.parseInt(s2[j - 1]);
            }
        }

        for(int i = 1;i <= n;i ++)
        {
            get_min(w[i],row_min[i],m);
            get_max(w[i],row_max[i],m);
        }

        int[] a = new int[N];
        int[] b = new int[N];//所有列滑动窗口后的最小值
        int[] c = new int[N];//所有列滑动窗口后的最大值
        int res = INF;
        //从第k列开始
        for(int i = k;i <= m;i ++)
        {
            for(int j = 1;j <= n;j ++) a[j] = row_min[j][i];
            get_min(a,b,n);

            for(int j = 1;j <= n;j ++) a[j] = row_max[j][i];
            get_max(a,c,n);

            for(int j = k;j <= n;j ++) res = Math.min(res, c[j] - b[j]);
        }
        System.out.println(res);
    }
}