二维区间最值差

一 问题描述

约翰正在寻找最平坦的土地种植玉米，他花了很大的代价调查它的 N*N 公顷方形农场。每公顷都有一个整数高度，有 K 组查询。整数 B 是方形田地的一个边长。查询 B*B 子矩阵中最大高度和最小高度的差值。

二 输入和输出

1 输入

第 1 行包含 3 个整数，N、B 和 K。第 2 到 N+1 行，每行都包含 N 个整数，代表 N*N 公顷每公顷的高度，每行的第 1 个整数都表示第 1 列，第 2 个整数都表示第 2 列。接下来的 K 行，每行都包含两个整数，分别表示查询子矩阵左上角和的行和列。

2 输出

对每个查询，都单行输出子矩阵中最大高度和最小高度的差值。

三 输入和输出样例

1 输入样例

5 3 1

5 1 2 6 3

1 3 5 2 7

7 2 4 6 1

9 9 8 6 5

0 6 9 3 9

1 2

2 输出样例

5

四 问题分析

本问题属于二维区间最值查询问题，可以使用 ST 解决，只不过增加了一维，且查询时需要注意区间问题。Fmax[k][i][j] 表示第 k 行[i,i+2^j-1]区间的最大值，区间长度为 2^j。

五 算法设计

1 求出数据范围内所有数的 log 值，将其存储在 lb[] 中。

2 将每个元素 a[k][k] 都存入 F[k][i][0] 中。

3 创建二维 ST。

4 从当前位置(x,y)开始，向右 B 列，向下 B 行，查询每一行的最大值和最小值，再求区间最大值和最小值。输出二维区间的最大值和最小值之差。

六 代码

package com.platform.modules.alg.alglib.poj2019;
 
public class Poj2019 {
    public String output = "";
 
    private final int maxn = 260;
 
    int a[][] = new int[maxn][maxn];
    int lb[] = new int[maxn];
    int Fmax[][][] = new int[maxn][maxn][11];
    int Fmin[][][] = new int[maxn][maxn][11];
 
 
    // 求解所有 log 值,保存到数组 lb[]
    void Initlog() {
        lb[0] = -1;
        for (int i = 1; i < maxn; i++)
            lb[i] = (i & (i - 1)) > 0 ? lb[i - 1] : lb[i - 1] + 1;
    }
 
    void ST(int n) {
        for (int k = 1; k <= n; k++) // 多一维
            for (int i = 1; i <= n; i++)
                Fmax[k][i][0] = Fmin[k][i][0] = a[k][i];
        for (int k = 1; k <= n; k++)
            for (int j = 1; j <= lb[n]; j++)
                for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                    Fmax[k][i][j] = Math.max(Fmax[k][i][j - 1], Fmax[k][i + (1 << (j - 1))][j - 1]);
                    Fmin[k][i][j] = Math.min(Fmin[k][i][j - 1], Fmin[k][i + (1 << (j - 1))][j - 1]);
                }
    }
 
    // 从坐标为(x,y)的地方开始，右下扩展 B 长度
    void solve(int x, int y, int B) {
        int k = lb[B];
        int maxx = -1;
        int minx = 0x3f3f3f3f;
        int l = y, r = y + B - 1;
        for (int i = x; i < x + B; i++) { // 查询每一行的最值
            maxx = Math.max(maxx, Math.max(Fmax[i][l][k], Fmax[i][r - (1 << k) + 1][k]));
            minx = Math.min(minx, Math.min(Fmin[i][l][k], Fmin[i][r - (1 << k) + 1][k]));
        }
        output += (maxx - minx) + "\n";
    }
 
    public String cal(String input) {
        int N, B, K;
        int x, y; // 每次查询的坐标
        Initlog();
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        N = Integer.parseInt(words[0]);
        B = Integer.parseInt(words[1]);
        K = Integer.parseInt(words[2]);
 
        for (int i = 1; i <= N; i++){
            String[] nums = line[i].split(" ");
            for (int j = 1; j <= N; j++){
                a[i][j] = Integer.parseInt(nums[j-1]);
            }
 
 
        }
        ST(N);
        for (int i = 0; i < K; i++) {
            String[] query = line[1 + N+i].split(" ");
            x = Integer.parseInt(query[0]);
            y = Integer.parseInt(query[1]);
            solve(x, y, B);
        }
        return output;
    }
}

七 测试