C++で解く「次に大きい要素 II」：循環配列のNext Greater Element問題

問題概要

循環配列（最後の要素の次は配列の最初の要素に戻る配列）が与えられたとき、各要素に対して「次に大きい数（Next Greater Number）」を求めて表示することを考えます。

ある数 x の次に大きい数とは、走査順において x より後で最初に現れる、x より大きな値のことです。このとき配列は循環しているため、末尾を超えたら先頭に戻って探索を続けることができます。もし次に大きい数が存在しない場合は -1 を返します。

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

• 最初の「1」の次に大きい数は「2」
• 「2」の次に大きい数は「3」（循環して探索）
• 最大値「3」より大きい数は存在しないため「-1」

解法のアプローチ：単調スタック

この問題は単調減少スタック（Monotonic Stack）を使うことで効率的に解けます。ポイントは、配列をあたかも2周分あるかのように扱い、インデックスを i % n で循環させることです。

具体的な手順は以下の通りです。

• n := 配列のサイズとする
• サイズ n の配列 res を定義し、すべて -1 で初期化する。また空のスタック st を用意する
• i を 0 から 2n-1 まで繰り返す
  • index := i mod n、x := nums[index] とする
  • スタックが空でなく、かつ nums[スタックの先頭] < x である間、次を繰り返す
    • res[スタックの先頭] := x と更新する
    • スタックの先頭要素を取り除く（pop）
  • index をスタックに push する
• 最後に res を返す

この方法では、スタックには「まだ次に大きい数が見つかっていない要素のインデックス」が降順に保持されます。より大きな値 x が出現するたびに、スタック上の小さい要素たちの答えが確定していきます。

C++による実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> nextGreaterElements(vector<int>& nums) {
      int n = nums.size();
      vector <int> res(n, - 1);
      stack <int> st;
      for(int i = 0; i < 2 * n; i++){
         int idx = i % n;
         int x = nums[idx];
         while(!st.empty() && nums[st.top()] < x){
            res[st.top()] = x;
            st.pop();
         }
         st.push(idx);
      }
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1,3,2,1};
   print_vector(ob.nextGreaterElements(v));
}

入力

[1,2,1,3,2,1]

出力

[2,3,3,-1,3,2]

計算量の分析

• 時間計算量： O(n)。ループは最大 2n 回回りますが、各要素はスタックに高々2回pushされ、2回popされるだけなので、全体として線形時間で処理できます。
• 空間計算量： O(n)。結果格納用の配列とスタックが必要です。

全要素ごとに毎回線形探索を行う素朴な O(n²) のアプローチと比べ、単調スタックを活用することで大幅に効率化できるのがこの手法の魅力です。