algorithm - 在矩阵的任何子矩阵中找到最大元素

Question

我给出了一个 N x M 的矩阵。对于从位置 (a, b) 开始的长度 X 的子矩阵，我必须找到子矩阵中存在的最大元素。

我的方法:

1. 按照问题说的去做: 简单的 2 个循环

   for(i in range(a, a + x))
   for(j in range(b, b + x)) max = max(max,A[i][j]) // N * M

一点进步:

 1. Make a segment tree for every i in range(0, N)
 2. for i in range(a, a + x) query(b, b + x)    // N * logM

是否有更好的解决方案只有 O(log n) 复杂度？

Answer 1

稀疏表算法方法 :- <O( N x M x log(N) x log(M)) , O(1)> .

预计算时间 - O( N x M x log(N) x log(M))
查询时间 - O(1)

要了解此方法，您应该具备使用稀疏表算法为一维查找 RMQ 的知识。

我们可以使用二维稀疏表算法来寻找范围最小查询。

我们在 One Dimension 中做什么:-
我们为长度为 2^k 的子数组预处理 RMQ使用动态规划。我们将保留一个数组 M[0, N-1][0, logN]其中 M[i][j]是从 i 开始的子数组中最小值的索引. 用于计算 M[i][j]我们必须在区间的前半部分和后半部分搜索最小值。很明显小块有2^(j – 1)长度，所以计算的伪代码是:-

if (A[M[i][j-1]] < A[M[i + 2^(j-1) -1][j-1]])
    M[i][j] = M[i][j-1]
else 
    M[i][j] = M[i + 2^(j-1) -1][j-1]

在这里A是存储值的实际数组。一旦我们对这些值进行了预处理，让我们展示如何使用它们来计算 RMQ(i, j)。这个想法是选择两个完全覆盖区间 [i..j] 的 block 。并找到它们之间的最小值。让k = [log(j - i + 1)] .为了计算RMQ(i, j)，我们可以使用以下公式:-

if (A[M[i][k]] <= A[M[j - 2^k + 1][k]])
    RMQ(i, j) = A[M[i][k]]
else 
    RMQ(i , j) = A[M[j - 2^k + 1][k]]

对于二维:-
类似地，我们也可以将上述规则扩展到 2 维，这里我们为长度为 2^K, 2^L 的子矩阵预处理 RMQ使用动态规划并保留数组 M[0,N-1][0, M-1][0, logN][0, logM] .在哪里M[x][y][k][l]是从 [x , y] 开始的子矩阵中最小值的索引并且有长度2^K, 2^L分别。 计算伪代码M[x][y][k][l]是:-

M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1])

在这里GetMinimum函数将从提供的元素中返回最小元素的索引。现在我们已经进行了预处理，让我们看看如何计算RMQ(x, y, x1, y1)。这里[x, y]子矩阵的起点和[x1, y1] represented end point of sub matrix 表示子矩阵的右下角点。这里我们必须选择四个完全覆盖[x, y, x1, y1]的子矩阵 block 。并找到它们中的最小值。让k = [log(x1 - x + 1)] & l = [log(y1 - y + 1)] .为了计算 RMQ(x, y, x1, y1) 我们可以使用以下公式:-

RMQ(x, y, x1, y1) = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);

上述逻辑的伪代码:-

// remember Array 'M' store index of actual matrix 'P' so for comparing values in GetMinimum function compare the values of array 'P' not of array 'M' 
SparseMatrix(n , m){ // n , m is dimension of matrix.
    for i = 0 to 2^i <= n:
        for j = 0 to 2^j <= m:
            for x = 0 to x + 2^i -1 < n :
                for y = 0 to y + (2^j) -1 < m:
                    if i == 0 and j == 0:
                        M[x][y][i][j] = Pair(x , y) // store x, y
                    else if i == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i][j-1], M[x][y+(2^(j-1))][i][j-1])
                    else if j == 0:
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j], M[x+ (2^(i-1))][y][i-1][j])
                    else 
                        M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1]);
}
RMQ(x, y, x1, y1){
    k = log(x1 - x + 1)
    l = log(y1 - y + 1)
    ans = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);
    return P[ans->x][ans->y] // ans->x represent Row number stored in ans and similarly ans->y represent column stored in ans
}