C++で解く「132パターン」問題：累積最小値とスタックを使った効率的なアルゴリズム

132パターンとは

n個の整数からなる数列 a₁, a₂, ..., a_n を考えます。「132パターン」とは、i < j < k を満たす部分列 a_i, a_j, a_k のうち、a_i < a_k < a_j が成り立つものを指します。つまり、「小さい値 → 大きい値 → 中間の値」という順序で並ぶ3つの要素が数列内に存在するかどうかを判定するアルゴリズムを設計するのが課題です。

例として、入力が [-1, 3, 2, 0] の場合を考えてみましょう。このとき [-1, 3, 2]、[-1, 3, 0]、[-1, 2, 0] という3つのパターンが存在するため、出力は true となります。

解法のアプローチ

この問題は、累積最小値の配列とスタックを組み合わせることで効率的に解けます。考え方のポイントは次の通りです。

• minVals配列： 各位置までの最小値（パターンの「1」に相当する候補）を前計算しておきます。

• スタック： 数列を右から左へ走査しながら、パターンの「3」（中間の大きな値）の候補を管理します。

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

• n := nums のサイズとする。n が 0 なら false を返す。

• サイズ n の配列 minVals を定義し、minVals[0] := nums[0] とする。

• i を 1 から n−1 までループさせる。

  • minVals[i] := minVals[i − 1] と nums[i] の最小値とする。

• スタック st を作成する。

• i を n − 1 から 1 まで逆順にループさせる。

  • minVal := minVals[i − 1]（位置 i より左側の最小値）。

  • curr := nums[i]（現在注目している値）。

  • st が空でなく、スタックの先頭が minVal 以下である間、pop を繰り返す。

  • st が空でなく、スタックの先頭が curr より小さければ true を返す。

  • nums[i] をスタックに push する。

• ループが完了したら false を返す。

この処理では、スタックの先頭に残った値が「2」の候補、minVal が「1」の候補、curr が「3」の候補として機能します。スタックから minVal 以下の値を除去することで、確実に「1」より大きい「2」だけが残るため、条件判定が正しく行えます。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool find132pattern(vector<int>& nums) {
      int n = nums.size();
      if(!n) return false;
      vector <int> minVals(n);
      minVals[0] = nums[0];
      for(int i = 1; i < n; i++){
         minVals[i] = min(minVals[i - 1], nums[i]);
      }
      stack <int> s;
      for(int i = n - 1; i > 0; i--){
         int minVal = minVals[i - 1];
         int curr = nums[i];
         while(!s.empty() && s.top() <= minVal) s.pop();
         if(!s.empty() && s.top() < curr) return true;
         s.push(nums[i]);
      }
      return false;
   }
};
main(){
   vector<int> v = {-1,3,2,0};
   Solution ob;
   cout << (ob.find132pattern(v));
}

入力

[-1,3,2,0]

出力

1

出力が「1」、すなわち true となり、数列 [-1, 3, 2, 0] には132パターンが存在することが確認できます。この手法により、全ての組み合わせを総当たりで調べる O(n²) 以上の計算量を避け、O(n) で効率的に判定できる点が大きな利点です。