JavaScriptで配列を昇順（増加列）に変換できるか判定する方法

本記事では、整数型の配列を引数として受け取り、「要素を最大1つだけ変更することで配列を昇順（増加列）にできるか」を判定するJavaScript関数の実装方法を解説します。

増加列（Increasing Sequence）とは

配列が増加列であるとは、すべてのインデックス i（0 ≤ i ≤ n − 2）に対して、次の条件が成り立つことを指します。

arr[i] <= arr[i + 1]

つまり、隣り合う要素を左から右へ見たときに値が減少することが一度もない（単調非減少＝広義の昇順）状態のことです。等しい値が並んでいても問題ありません。

問題の定義

整数の配列 arr を第一引数（唯一の引数）として受け取るJavaScript関数を作成します。この関数は、配列の要素を最大1つだけ変更することで、配列全体を増加列に変換できるかどうかを判定します。

• 変換できれば true を返す
• 変換できなければ false を返す

入出力例

入力

const arr = [8, 3, 3, 7, 9];

出力

const output = true;

出力の説明

インデックス0にある「8」を「1」や「2」などに置き換えることで、[1, 3, 3, 7, 9] のような昇順の配列を得られます。そのため、この入力に対する答えは true となります。

実装例

以下がコードです。

const arr = [8, 3, 3, 7, 9];

const canConvert = (arr = []) => {
   // 配列全体が現時点で昇順かどうかを調べるヘルパー関数
   const find = () => {
      for (let i = 1; i < arr.length; i++) {
         if (arr[i] < arr[i - 1]) {
            return false;
         }
      }
      return true;
   };

   // 減少している箇所（arr[i] < arr[i - 1]）を探す
   for (let i = 0; i < arr.length; i++) {
      if (arr[i] < arr[i - 1]) {
         // パターン1: 後ろの要素を前の要素に合わせて引き上げる
         const temp = arr[i];
         arr[i] = arr[i - 1];
         if (find()) {
            return true;
         }
         // パターン2: 元に戻したうえで、前の要素を後ろの要素に合わせて下げる
         arr[i] = temp;
         arr[i - 1] = arr[i];
         return find();
      }
   }
   // 減少箇所がなければ、すでに昇順なので true
   return true;
};

console.log(canConvert(arr));

出力

true

アルゴリズムのポイント

このコードの考え方を整理すると、次の手順になります。

1. 配列を先頭から走査し、「arr[i] < arr[i − 1]」という減少箇所を探します。
2. 減少箇所が見つからなければ、配列はすでに昇順なので true を返します。
3. 見つかった場合、修正方法は2通りあります。
   • 後ろの要素を上げる：arr[i] を arr[i − 1] と同じ値に変更し、全体が昇順になるか確認する。
   • 前の要素を下げる：arr[i − 1] を arr[i] と同じ値に変更し、再度全体を確認する。
4. どちらか一方でも成功すれば true、両方とも失敗すれば false を返します。

計算量は O(n) で、減少箇所の処理は高々1回しか行われないため、非常に効率的なアルゴリズムです。なお、この実装は渡された元の配列を直接書き換える点に注意してください。元の配列を保持したい場合は、事前にコピーしておくと安全です。