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です。

作成できたチャンクの最大数はいくつですか？

これを解決するには、次の手順に従います-

• ans：=0、minVal：=inf、n：=arrのサイズ、maxVal：=-inf
• 0からnの範囲のiの場合
  • maxVal：=arr[i]とmaxValの最大値
  • maxVal =iの場合、ansを1増やします
• 回答を返す

例

理解を深めるために、次の実装を見てみましょう-

#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