JavaScriptの配列から3つの厳密に増加する数（連続・非連続問わず）を見つける方法

問題の概要

まず、次のような数値の配列を用意します。

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

求められているのは、このような数値の配列を受け取り、インデックスと値の両方が厳密に増加している3つの数を見つけ出すJavaScript関数です。なお、3つの数は必ずしも隣り合っている必要はなく、離れた位置にあっても構いません。

上記の配列の場合、7・8・9という数値はそれぞれインデックス1・3・4に位置しています。インデックスも値も並び順に沿って大きくなっているため、両方の条件を満たしています。したがって、この配列に対して関数は true を返すべきです。

解決策：貪欲法による実装

この問題は、配列を先頭から一度だけ走査しながら、それまでに現れた「最小値」と「2番目に小さい値」を追跡する貪欲法（グリーディ法）で効率的に解けます。計算量はO(n)、追加メモリはO(1)と非常にシンプルです。

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

const findMatch = (arr) => {
  let first = Infinity;   // 1つ目の候補（これまでの最小値）
  let second = Infinity;  // 2つ目の候補
  for (const num of arr) {
    if (num <= first) {
      first = num;
    } else if (num <= second) {
      second = num;
    } else {
      // first < second < 現在の値 となる3つの組が見つかった
      return true;
    }
  }
  return false;
};

console.log(findMatch(arr));

実行結果

コンソールには次のように表示されます。

true

コードの仕組み

• first: それまでに読み込んだ数の中で最も小さい値を保持します。
• second: firstより後の位置に出現し、かつfirstより大きい値のうち最小のものを保持します。
• ある要素が second よりも大きい場合、「first ＜ second ＜ 現在の値」という関係がインデックス順にも成立しているため、その時点で true を返せます。

配列の長さが3未満の場合や、条件を満たす組み合わせが存在しない場合は、ループが完了しても true にならないため、最終的に false が返されます。このアルゴリズムは連続しない（飛び飛びの）インデックスの組み合わせも正しく扱える点がポイントです。