C++で配列を分割してソートする際の最大チャンク数を求める方法

問題の概要

[0, 1, ..., arr.length - 1] の順列（パーミュテーション）である配列 arr が与えられたとします。この配列をいくつかの「チャンク（区切り）」に分割し、それぞれのチャンクを個別にソートします。その後、すべてのチャンクを連結した結果が、完全にソートされた配列になるとき、作成できるチャンク数の最大値を求めるのがこの問題です。

例えば、配列が [1,0,2,3,4] の場合、出力は 4 になります。[1, 0] と [2,3,4] のように2つのパーティションに分割することもできますが、[1, 0]、[2]、[3]、[4] のように4つに分割することも可能です。これが作成可能な最大チャンク数となるため、答えは 4 になります。

それでは、作成できるチャンク数の最大値はいくつになるのでしょうか？

解法のアプローチ

この問題を解くために、以下の手順に従います。

• ans := 0、minVal := 無限大、n := 配列のサイズ、maxVal := 負の無限大 として初期化します
• i を 0 から n までループさせます
  • maxVal := arr[i] と maxVal のうち大きい方を代入します
  • maxVal == i であれば、ans を 1 増やします
• 最後に ans を返します

このアルゴリズムが正しく動作する理由は、配列が [0, n-1] の順列であることにあります。インデックス i までの要素の最大値がちょうど i と一致するとき、その位置までの部分配列は「0 から i までの値をすべて含む集合」となり、そこで区切っても全体のソート結果に影響しないため、独立したチャンクとして扱えるのです。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxChunksToSorted(vector<int>& arr) {
      int ans = 0;
      int minVal = INT_MAX;
      int n = arr.size();
      int maxVal = INT_MIN;
      for(int i = 0; i < n; i++){
         maxVal = max(arr[i], maxVal);
         if(maxVal == i){
            ans++;
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,2,3,4};
   cout << (ob.maxChunksToSorted(v));
}

入力

[1,0,2,3,4]

出力

4

計算量について

このアルゴリズムは配列を一度走査するだけなので、時間計算量は O(n)、追加のデータ構造を使用しないため空間計算量は O(1) となります。非常に効率的な解法と言えるでしょう。