C++で配列を条件を満たす2つの部分配列に分割する方法

問題の概要

配列 A が与えられたとき、それを left と right という 2 つの部分配列に分割することを考えます。分割は以下の条件を満たす必要があります。

• left 部分配列のすべての要素は、right 部分配列のすべての要素以下である
• left と right はどちらも空であってはならない
• left のサイズは可能な限り小さくする

このような分割を行った後の left の長さを求めます。なお、条件を満たす分割が存在することは保証されています。

例えば、入力が [5,0,3,8,6] の場合、出力は 3 になります。このとき left は [5,0,3]、right は [8,6] となるためです。

アルゴリズムの考え方

この問題は、接頭辞最大値（prefix max）と接尾辞最小値（suffix min）を組み合わせることで、効率的に解くことができます。手順は以下の通りです。

1. n := A のサイズとし、サイズ n の配列 maxx を作成する
2. minVal := A の最後の要素とする
3. maxx[0] := A[0] とする
4. i が 1 から n-1 までの範囲で、maxx[i] := max(A[i], maxx[i-1]) と更新する（maxx[i] は A[0..i] の最大値を表す）
5. ans := A のサイズ - 1 で初期化する
6. i を n-1 から 1 まで逆順に処理する
   • minVal := min(minVal, A[i]) と更新する（minVal は A[i..n-1] の最小値を表す）
   • minVal >= maxx[i-1] が成り立つ場合、ans := i とする
7. ans を返す

実装例

以下に C++ による実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int partitionDisjoint(vector <int>& A) {
      int n = A.size();
      vector <int> maxx(n);
      int minVal = A[n - 1];
      maxx[0] = A[0];
      for(int i = 1; i < n; i++){
         maxx[i] = max(A[i], maxx[i - 1]);
      }
      int ans = A.size() - 1;
      for(int i = n - 1; i >= 1; i--){
         minVal = min(minVal, A[i]);
         if(minVal >= maxx[i - 1]){
            ans = i;
         }
      }
      return ans;
   }
};
main(){
   vector<int> v1 = {5,0,3,8,6};
   Solution ob;
   cout << (ob.partitionDisjoint(v1));
}

入力

[5,0,3,8,6]

出力

3

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。配列を前方向と後ろ方向にそれぞれ 1 回ずつ走査するだけで済むため、大規模な入力に対しても効率的に動作します。