求矩阵的任意SubMatrix中的最大元素

Question

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

我的方法：

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 )复杂度？

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。

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

我们在一维中所做的事情：-

我们使用动态编程对长度为的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是存储values.Once的实际数组，我们对这些值进行了预处理，让我们展示如何使用它们来计算RMQ(i，j)。这样做的目的是选择两个完全覆盖间隔[i..j]的块，并在它们之间找到最小值。让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^K, 2^L的子矩阵进行了预处理&保持数组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]表示子矩阵的端点，表示子矩阵的右下角。在这里，我们必须选择四个子矩阵块，它们完全覆盖[x, y, x1, y1]并找到其中的最小值。让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
}

Answer 2

下面是c++中的示例代码，用于@Chapta提供的伪代码，这是一些用户所要求的。

int M[1000][1000][10][10];
int **matrix;

void precompute_max(){
    for (int i = 0 ; (1<<i) <= n; i += 1){
        for(int j = 0 ; (1<<j) <= m ; j += 1){
            for (int x = 0 ; x + (1<<i) -1 < n; x+= 1){
                for (int y = 0 ;  y + (1<<j) -1 < m; y+= 1){
                    if (i == 0 and j == 0)
                        M[x][y][i][j] = matrix[x][y]; // store x, y
                    else if (i == 0)
                        M[x][y][i][j] = max(M[x][y][i][j-1], M[x][y+(1<<(j-1))][i][j-1]);
                    else if (j == 0)
                        M[x][y][i][j] = max(M[x][y][i-1][j], M[x+ (1<<(i-1))][y][i-1][j]);
                    else 
                        M[x][y][i][j] = max(M[x][y][i-1][j-1], M[x + (1<<(i-1))][y][i-1][j-1], M[x][y+(1<<(j-1))][i-1][j-1], M[x + (1<<(i-1))][y+(1<<(j-1))][i-1][j-1]);
                    // cout << "from i="<<x<<" j="<<y<<" of length="<<(1<<i)<<" and length="<<(1<<j) <<"max is: " << M[x][y][i][j] << endl;
                }
            }
        }
    }
}

int compute_max(int x, int y, int x1, int y1){
    int k = log2(x1 - x + 1);
    int l = log2(y1 - y + 1);
    // cout << "Value of k="<<k<<" l="<<l<<endl;
    int ans = max(M[x][y][k][l], M[x1 - (1<<k) + 1][y][k][l], M[x][y1 - (1<<l) + 1][k][l], M[x1 - (1<<k) + 1][y1 - (1<<l) + 1][k][l]);
    return ans;
}

此代码首先预计算二维稀疏表，然后在恒定时间内查询它。附加信息:稀疏表存储最大元素，而不是最大元素的索引。

Answer 3

AFAIK，不可能有O(logn方法)，因为矩阵不遵循顺序。但是，如果您有这样一个顺序，即每一行从左到右按升序排序，而每列从上到下依次排列，那么您就知道Aa+x (子矩阵的右下角单元格)是该子矩阵中最大的元素。因此，求最大值需要O(1)时间，一旦矩阵被排序。但是，如果没有对矩阵进行排序，则需要花费O(NxM log{NxM})