JavaScriptで増加するトリプレットが存在するか判定する方法

増加数列とは

各要素が直前の要素以上の値を持つ数列のことを「増加数列」と呼びます。

例えば、次のような数列が挙げられます。

4, 6, 8, 9, 11, 14 は増加数列です
3, 3, 3, 3, 3, 3, 3 も増加数列です

問題

数値の配列 arr を唯一の引数として受け取るJavaScript関数を作成する必要があります。この関数は、配列内に「増加する3つの要素(トリプレット)」が存在するかどうかを判定して返します。

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

const arr = [4, 1, 5, 7, 3, 1, 4];

出力は次のようになります −

const output = true;

出力の説明

配列内に 1, 5, 7 という連続する増加要素が存在するため、結果は true となります。

例

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

const arr = [4, 1, 5, 7, 3, 1, 4];
const increasingTriplet = function(arr) {
   let first = Infinity;
   let second = Infinity;
   for (let curr of arr) {
      if (curr > second && curr > first) {
         return true;
      };
      if (curr > first) {
         second = curr;
      }else{
         first = curr;
      };
   };
   return false;
};
console.log(increasingTriplet(arr));

コードの解説

このアルゴリズムでは、貪欲法(グリーディー法)を用いて配列を一度だけ走査します。変数 first には「最も小さい候補値」を、変数 second には「first より大きい2番目の候補値」をそれぞれ保持します。

ループの各反復で確認する条件は次のとおりです −

現在の要素が second よりも大きければ、first < second < 現在の要素 という増加トリプレットが成立していることになるため true を返します。そうでなければ、現在の値を first または second のいずれか適切な方に更新していきます。

つまり、0 ≤ i < j < k ≤ n-1 を満たす i, j, k が存在し、arr[i] < arr[j] < arr[k] となる場合は true を返し、最後まで見つからなければ false を返します。

この手法の計算量は時間 O(n)、空間 O(1) であり、非常に効率的です。

出力

コンソールへの出力は次のとおりです −

true