找到最大的子矩阵算法

Question

我有一个N*N矩阵(N = 2到10000)的数字,范围从0到1000.如何找到由相同数字组成的最大(矩形)子矩阵？

例:

     1  2  3  4  5
    -- -- -- -- --
1 | 10  9  9  9 80
2 |  5  9  9  9 10
3 | 85 86 54 45 45
4 | 15 21  5  1  0
5 |  5  6 88 11 10

输出应该是子矩阵的区域,后面是其左上角元素的基于1的坐标.例如,这是(6, 2, 1)因为有6个9位于第2列第1行.

Answer 1

这是一个正在进行的工作

我思考过这个问题，我想我可能有一个O(w*h)算法。

这个想法是这样的：

• 对于任何计算，从 开始的(i,j)列中具有相同值的单元格的最大数量。将此值存储为j(i,j)heights[i][j].
• 创建子矩阵的空向量（lifo）
• 对于所有行：我
  • 对于所有列：j
    • 弹出所有height > heights[i][j]. 因为子矩阵的高度 >heights[i][j]不能在这个单元格上继续
    • 推入一个子矩阵，(i,j,heights[i][j])该j子矩阵由我们可以拟合高度子矩阵的最远坐标定义：heights[i][j]
    • 更新当前最大子矩阵

棘手的部分在于内循环。我使用类似于最大子窗口算法的东西来确保它是O(1)每个单元格的平均值。

我将尝试提出一个证明，但同时这是代码。

#include <algorithm>
#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>

typedef std::vector<int>   row_t;
typedef std::vector<row_t> matrix_t;

std::size_t height(matrix_t const& M) { return M.size(); }
std::size_t width (matrix_t const& M) { return M.size() ? M[0].size() : 0u; }

std::ostream& operator<<(std::ostream& out, matrix_t const& M) {
  for(unsigned i=0; i<height(M); ++i) {
    std::copy(begin(M[i]), end(M[i]),
          std::ostream_iterator<int>(out, ", "));
    out << std::endl;
  }
  return out;
}

struct sub_matrix_t {
  int i, j, h, w;
  sub_matrix_t(): i(0),j(0),h(0),w(1) {}
  sub_matrix_t(int i_,int j_,int h_,int w_):i(i_),j(j_),h(h_),w(w_) {}
  bool operator<(sub_matrix_t const& rhs) const { return (w*h)<(rhs.w*rhs.h); }
};


// Pop all sub_matrix from the vector keeping only those with an height
// inferior to the passed height.
// Compute the max sub matrix while removing sub matrix with height > h
void pop_sub_m(std::vector<sub_matrix_t>& subs,
           int i, int j, int h, sub_matrix_t& max_m) {

  sub_matrix_t sub_m(i, j, h, 1);

  while(subs.size() && subs.back().h >= h) {
    sub_m = subs.back();
    subs.pop_back();
    sub_m.w = j-sub_m.j;
    max_m = std::max(max_m, sub_m);
  }

  // Now sub_m.{i,j} is updated to the farest coordinates where there is a
  // submatrix with heights >= h

  // If we don't cut the current height (because we changed value) update
  // the current max submatrix
  if(h > 0) {
    sub_m.h = h;
    sub_m.w = j-sub_m.j+1;
    max_m = std::max(max_m, sub_m);
    subs.push_back(sub_m);
  }
}

void push_sub_m(std::vector<sub_matrix_t>& subs,
        int i, int j, int h, sub_matrix_t& max_m) {
  if(subs.empty() || subs.back().h < h)
    subs.emplace_back(i, j, h, 1);
}

void solve(matrix_t const& M, sub_matrix_t& max_m) {
  // Initialize answer suitable for an empty matrix
  max_m = sub_matrix_t();
  if(height(M) == 0 || width(M) == 0) return;

  // 1) Compute the heights of columns of the same values
  matrix_t heights(height(M), row_t(width(M), 1));
  for(unsigned i=height(M)-1; i>0; --i)
    for(unsigned j=0; j<width(M); ++j)
      if(M[i-1][j]==M[i][j])
    heights[i-1][j] = heights[i][j]+1;

  // 2) Run through all columns heights to compute local sub matrices
  std::vector<sub_matrix_t> subs;
  for(int i=height(M)-1; i>=0; --i) {
    push_sub_m(subs, i, 0, heights[i][0], max_m);
    for(unsigned j=1; j<width(M); ++j) {
      bool same_val  = (M[i][j]==M[i][j-1]);
      int pop_height = (same_val) ? heights[i][j] : 0;
      int pop_j      = (same_val) ? j             : j-1;
      pop_sub_m (subs, i, pop_j, pop_height,    max_m);
      push_sub_m(subs, i, j,     heights[i][j], max_m);
    }
    pop_sub_m(subs, i, width(M)-1, 0, max_m);
  }
}

matrix_t M1{
  {10,  9,  9,  9, 80},
  { 5,  9,  9,  9, 10},
  {85, 86, 54, 45, 45},
  {15, 21,  5,  1,  0},
  { 5,  6, 88, 11, 10},
};

matrix_t M2{
  {10, 19,  9, 29, 80},
  { 5,  9,  9,  9, 10},
  { 9,  9, 54, 45, 45},
  { 9,  9,  5,  1,  0},
  { 5,  6, 88, 11, 10},
};


int main() {
  sub_matrix_t answer;

  std::cout << M1 << std::endl;
  solve(M1, answer);
  std::cout << '(' << (answer.w*answer.h)
        << ',' << (answer.j+1) << ',' << (answer.i+1) << ')'
        << std::endl;

  answer = sub_matrix_t();
  std::cout << M2 << std::endl;
  solve(M2, answer);
  std::cout << '(' << (answer.w*answer.h)
        << ',' << (answer.j+1) << ',' << (answer.i+1) << ')'
        << std::endl;
}