동일한 정수를 갖는 서브 매트릭스의 최대 크기

Question

정수가 들어있는 MxN 크기의 매트릭스가 있습니다. 우리는 같은 정수를 가진 가장 큰 크기의 부분 행렬을 찾아야합니다. 예를 들면 다음과 같습니다.

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

여기서 가장 큰 부분 행렬은 2를 모두 포함하는 3x2 크기입니다. 내 생각은 arr [i] [j + 1], arr [i + 1] arr [j + 1] 및 arr [i + 1] [j]가 각 요소 arr [i] [j] 같거나 틀리다. 그것들이 같으면 우리는 어떻게해서 행렬의 최대 크기를 업데이트 할 수 있습니다. 그러나 나는 정확한 해결책에 도달 할 수 없었다.

어떻게 든 동적 프로그래밍을 사용할 수 있는지 궁금합니다. 이것은 인터뷰 질문이었습니다.

Answer 1

1. 부분 행렬의 맨 아래 행이 고정되어 있다고 가정합시다. 그런 다음 각 열은 쌍 (값, 높이)으로 표현 될 수 있습니다. 여기서 value는이 행과 열의 요소 값이고 height는이 열의 연속 요소 수와 동일합니다. 상기 값은 예를 들어, 행렬은

   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)} 및 { 이제 우리는 표준 문제를 해결할 수 있습니다 : 값 배열 h[i]이 주어지면 각 그룹 내에서 i 및 j에 대해 min(h[i], h[i + 1], ..., h[j]) * (j - i + 1)의 가장 큰 값을 찾습니다 (스택을 사용하는 선형 솔루션이 있습니다. 자세한 내용은 다음을 참조하십시오). 선형 시간에 하나의 행을 처리 할 수 ​​있습니다.

3. 마지막으로 필요한 것은 각 행의 (값, 높이) 배열을 효율적으로 계산하는 것입니다. 첫 번째 행에 대해서는 사소한 것입니다 따라서 모든 행과 행을 하나씩 반복 할 수 있습니다. (한 요소가 열의 맨 아래에 추가되면 (값, 높이) 쌍이 두 가지 방법으로 변경됩니다. 즉, (new_value, 1) 또는 (value, height + 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 
}