algorithm - 具有相同整数的最大子矩阵

Question

有一个 MxN 大小的矩阵，其中包含整数。我们需要找到其中具有相同整数的最大尺寸子矩阵。例如:

1 2 2 4 5
1 2 2 8 7
3 2 2 6 1

这里最大的子矩阵大小为 3x2，其中全部为 2。我的想法是检查每个元素 arr[i][j] ， arr[i][j+1] 、 arr[i+1]arr[j+1] 和 arr[i+1][j] 是否是相等与否。如果它们相等，那么我们可以以某种方式更新矩阵的最大大小。但我无法得出确切的解决方案。

我想知道我们是否可以利用动态编程。这是一个面试问题。

Answer 1

1. 假设子矩阵的底行是固定的。那么每一列都可以表示为一对(值，高度)，其中值是该行和列中元素的值，高度是该列中有多少个连续元素等于它。例如，如果矩阵是

   3 1 2 3 
   1 2 2 1
   3 2 2 1
   2 2 2 2
   

   我们看到的底行是 2(从零开始的索引)，值分别是 (3, 1)、(2, 2)、(2, 3) 和 (1, 2)。

2. 让我们将列分成几组，将具有相同值的相邻元素分组在一起(对于前面的示例，它是 {(3, 1)}、{(2, 2)、(2, 3)} 和{(1, 2)}。现在我们可以解决一个标准问题:给定一个值数组 h[i]，找到 min(h[i], h[ i + 1], ..., h[j]) * (j - i + 1) 对于每个组内的所有 i 和 j(有是一种使用堆栈的线性解决方案，如果需要的话我可以详细说明这一点)。它允许我们在线性时间内处理一行。

3. 我们需要的最后一件事是有效地计算每行的(值，高度)数组。对于第一行来说这是微不足道的。因此，我们可以逐一迭代所有行和它们(当一个元素添加到列的底部时，(值，高度)对以两种可能的方式发生变化:它变成(new_value，1)或(值，高度+ 1))。

这些观察使我们能够在 O(M) 时间内处理一行。总时间复杂度为O(N * M)。

这是一些代码(它不是完整的实现，它可能包含错误):

int solve() {
    int res = 0;
    Pair[] valueForColumn = new Pair[rowsCount];
    for (int col = 0; col < columnsCount; col++)
        valueForColunm[col] = new Pair(matrix[0][col], 1);
    res = Math.max(res, solveForRow(valueForColumn); 
    for (int row = 1; row < rowsCount; row++) {
        for (int col = 0; col < columnsCount; col++)
            if (matrix[row][col] == matrix[row - 1][col]) {
                valueForColumn[col].second++;
            } else {
                valueForColumn[col].first = matrix[row][col];
                valueForColumn[col].second = 1;
            }
        }
        res = Math.max(res, solveForRow(valueForColumn));
   }
   return res;
}

int solveForRow(Pair[] valueForColumn) {
    List<Integer> group = new ArrayList<>();
    int res = 0;
    for (int i = 0; i < valueForColumn.length; i++) {
        group.add(valueForColumn[i].second);
        if (i == valueForColumn.length - 1 
                || valueForColumn[i].first != valueForColumn[i + 1].first) {
            res = Math.max(res, solveForGroup(group));
            group.clear();
        }
    }
    return res;
}

int solveForGroup(List<Integer> heights) {
    // a stack-based algorithm 
    // with linear time complexity mentioned in 2. goes here
}