JavaScriptで最大num個の0を1に変更した後の最長連続1の長さを求める方法

問題

JavaScriptの関数を作成します。この関数は、0と1のみを含むバイナリ配列arrを第一引数に、数値numを第二引数として受け取ります。

配列内の0を最大num個まで1に変更できるとき、変更後の配列において1のみが連続する最長の(連続した)部分配列の長さを返す必要があります。

例えば、関数への入力が以下の場合 −

const arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0];
const num = 2;

このときの出力は以下のようになります −

const output = 6;

出力の説明

2つの0を1に変更すると、配列の末尾6要素がすべて1になるためです。

スライディングウィンドウによるアプローチ

この問題は「スライディングウィンドウ(尺取り法)」と呼ばれる手法で効率的に解けます。左右2つのポインタを使用し、ウィンドウ内に含まれる0の数がnumを超えない範囲でウィンドウを維持・拡張していきます。

コード例

この問題を解くコードは以下のとおりです −

const arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0];
const num = 2;
const longestOnes = (arr = [], num = 1) => {
   let max = 0;
   let left = 0;
   let curr = num;
   for(let right = 0; right < arr.length; right++){
      if(arr[right] === 0){
         curr -= 1;
      };
      while(curr < 0){
         if(arr[left] === 0){
            curr += 1;
         };
         left += 1;
      };
      max = Math.max(max, right - left + 1);
   };
   return max;
};
console.log(longestOnes(arr, num));

コードの解説

このアルゴリズムの動作を簡単に説明します:

• rightポインタで配列を先頭から順に走査し、要素が0であれば許容カウントcurrを1減らします。
• currが負になった場合、ウィンドウ内の0の数が許容数を超えているため、leftポインタを右に進め、0を通過するたびにcurrを1増やして回復させます。
• 各ステップで現在のウィンドウ幅(right - left + 1)を計算し、最大値maxを更新します。

この方法では各要素が最大2回しか走査されないため、時間計算量はO(n)、空間計算量はO(1)という非常に効率的な実装になります。

出力

コンソールには以下のように出力されます −

6