【Python】循環する配列で右側にある次の大きい要素を見つける方法

問題概要

数値のリスト nums が与えられます。これと同じ長さの新しいリストを作成し、インデックス i の位置には、nums[i] よりも大きい「右側の次の要素」を格納します。ここで重要なのは、リストの末尾に達したら先頭に戻って探索を続けるという循環（リング状）の扱いです。もし右側により大きい数が存在しない場合は -1 を設定します。

たとえば、入力が [4, 5, 1, 3] の場合、出力は [5, -1, 3, 4] となります。

• 4 の右側で最初に現れるより大きい数は 5
• 5 の右側にそれより大きい数はないので -1
• 1 の右側では 3
• 3 の右側では、末尾を超えて先頭に戻ると 4 が見つかる

アルゴリズム：単調スタックを使った解法

この問題は「単調スタック（monotonic stack）」と呼ばれるテクニックを使うと効率的に解けます。手順は以下の通りです。

1. n := 配列 a のサイズとします。
2. stack := スタック（初期値として 0 を挿入）、res := サイズ n のリストで、すべて -1 で初期化します。
3. 配列全体を 2 回走査します（循環を扱うため）。
   • i を 0 から n-1 まで繰り返します。
   • スタックが空でなく、a[スタックの先端] < a[i] である間、以下を繰り返します。
     • res[スタックの先端] := a[i]
     • スタックから最後の要素を取り除く
   • スタックの末尾に i を追加します。
4. res を返します。

ポイントは、配列を 2 回走査することで、末尾から先頭へ「折り返す」ケースも自然に処理できる点です。スタックにはまだ答えが確定していないインデックスが保持されており、より大きな値が出てきたタイミングで順番に答えを確定させていきます。

実装例

class Solution:
   def solve(self, a):
      n = len(a)
      stack, res = [0], [-1] * n
      for _ in range(2):
         for i in range(n):
            while stack and a[stack[-1]] < a[i]:
               res[stack[-1]] = a[i]
               stack.pop()
            stack.append(i)
   return res

ob = Solution()
nums = [4, 5, 1, 3]
print(ob.solve(nums))

入力

[4, 5, 1, 3]

出力

[5, -1, 3, 4]

計算量について

各要素は最大でも 2 回ずつスタックへの push / pop が行われるため、時間計算量は O(n)、必要なメモリも O(n) です。すべての要素同士を総当たりで比較する O(n²) の素朴なアプローチに比べて、大規模なデータでも高速に動作します。