programmer-最大正方形

問題の説明

表(プレート)は1と0で塗りつぶされます.表1は1 x 1の正方形からなる.表に1からなる最大正方形を見つけ、戻り幅の解関数を完了してください.△正方形とは、軸に平行な正方形のこと.

せいげんじょうけん

∙テーブル(board)は2次元配列です.
∙表(ボード)の行(行)のサイズ:1000以下の自然数
∙表(ボード)の列(列)の大きさ:1000以下の自然数
∙テーブル(board)の値は1または0のみです.

function solution(board){
  let max = 0;
  let i = 1;
  const width = board[0].length;
  const height = board.length;

  if(!board) return 0;

  if( height === 1){
    return 1;
  }

  while( i < height){

    for( let j = 1; j < width ; j++){
      if( board[i][j] === 1){
        board[i][j] = Math.min( board[i][j - 1], board[i - 1][j], board[i-1][j-1]) + 1;

        if(board[i][j] >= max){
          max = board[i][j];
        }
      }
    }

    i++;
  }

  return max * max;

}

2 D配列内のすべての要素に近づこうとしたが,正確な方法は考えられず,他の解法を参照した.
1)入力配列の行(高さ)が1の場合、正方形の最大幅は1に戻ります.
2)正方形の右下隅を中心として展開されるため、行(height)をループするiはインデックス1から最後のheight-1/列(width)まで同様にjを1から最後のinwidth-1までループする
3)各インデックスに対応する要素が1の場合、左、左上、右上をチェックします.なぜなら、この3つの値が1の場合、4つの正方形が集約され、2 x 2の矩形を定義することができ、その後、3 x 3、4 x 4、5 x 5、∙∙に拡張することができるからです.この周囲の3つの要素の最大値を求め、対応するインデックス要素とマージします.この演算値が既存のmaxと比較的大きい場合、maxが更新されます.

+) python version

def solution(board):
    maximum = 0
    i = 1
    width = len(board[0])
    height = len(board)
    
    if height == 0: return 0
    
    if height == 1: return 1
    
    while i < height:
        for j in range(1, width):
            if board[i][j] == 1:
                board[i][j] = min(board[i][j - 1], board[i - 1][j], board[i - 1][j - 1]) + 1
                
                if board[i][j] > maximum:
                    maximum = board[i][j]
        i += 1
        
    
    return maximum * maximum

リファレンス

1) https://angwangho.github.io/algorithm-最大正方形/
2) https://moonsupport.tistory.com/243?category=797569