JavaScriptで循環配列の「次に大きい要素」を求める方法

循環配列（Circular Array）とは

循環配列とは、最後の要素の「次」が配列の先頭の要素につながっている、まるで輪のように環状に並んだ配列のことを指します。

もちろん、実際にこのような形でデータを格納できる仕組みは存在しません。データは通常どおり連続したメモリ領域に保存されており、「循環配列」とは現実のデータ構造というよりも、あくまで考え方・発想として捉えるものです。

問題の定義

整数の循環配列 arr を第一引数（唯一の引数）として受け取り、元の配列の各要素に対応する「次に大きい要素（Next Greater Element）」を格納した配列を構築して返す関数を、JavaScriptで作成します。

ある数値 num の「次に大きい数」とは、走査順序（本記事では右方向）においてその数の直後に現れる、最初のより大きい数のことです。配列は循環しているため、末尾を超えたら先頭に戻って探索を続けることができます。それでも次に大きい数が存在しない場合は、その数に対して -1 を割り当てます。

たとえば、関数への入力が次の場合：

const arr = [7, 8, 7];

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

const output = [8, -1, 8];

出力の解説

配列内の2つの 7 の次に大きい要素は、どちらも 8 です。一方、8 より大きい要素は配列中に存在しないため、8 には -1 が設定されます。

実装例

const arr = [7, 8, 7];

const nextGreaterElement = (arr = []) => {
  const res = [];
  const stack = [];
  if (!arr || arr.length < 1) {
    return res;
  }
  // 1回目：左から右へ走査し、答えが確定した分だけ記録する
  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      const small = stack.pop();
      res[small] = arr[i];
    }
    stack.push(i);
  }
  // 2回目：循環をシミュレートするため、先頭からもう一度走査
  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      const small = stack.pop();
      res[small] = arr[i];
    }
  }
  // 残った要素には次に大きい要素が存在しないため -1 を設定
  const rem = stack.length;
  for (let i = 0; i < rem; i++) {
    res[stack.pop()] = -1;
  }
  return res;
};

console.log(nextGreaterElement(arr));

コードの解説

このアルゴリズムでは「単調スタック（Monotonic Stack）」というテクニックを活用しています。処理のポイントは以下のとおりです。

• 1回目のループ： 配列を左から右へ走査しながら、要素のインデックスをスタックに積んでいきます。現在の要素がスタックの先頭にある要素より大きければ、それはスタック内の要素にとって「次に大きい要素」に該当するため、res[small] に現在の値を記録します。
• 2回目のループ： 循環配列の性質を再現するため、配列の先頭からもう一度同じ処理を実行します。これにより、1周目で答えが見つからなかった要素についても、先頭側により大きい要素が存在すれば答えを埋めることができます。
• 最終処理： それでもスタックに残っている要素は、配列全体のどこにも自分より大きい要素が存在しないことを意味するため、-1 を代入します。

計算量

各要素は最大でも2回のループでそれぞれ1度ずつ push / pop されるため、時間計算量は O(n)、結果配列とスタックに必要な空間計算量も O(n) となります。

出力結果

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

[8, -1, 8]