。ソートする最大チャンク数

769。並べ替えるための最大チャンク

難易度: 中

トピック: 配列、スタック、貪欲、ソート、単調スタック

[0, n - 1] の範囲内の整数の順列を表す長さ n の整数配列 arr が与えられます。

arr をいくつかの チャンク (つまり、パーティション) に分割し、各チャンクを個別にソートします。それらを連結した後の結果は、ソートされた配列と等しくなるはずです。

配列をソートするために作成できるチャンクの最大数を返します。

例 1:

• 入力: arr = [4,3,2,1,0]
• 出力: 1
• 説明:
  2 つ以上のチャンクに分割すると、必要な結果が返されません。
  たとえば、[4, 3]、[2, 1, 0] に分割すると [3, 4, 0, 1, 2] となり、ソートされません。

例 2:

• 入力: arr = [1,0,2,3,4]
• 出力: 4
• 説明:
  [1, 0]、[2, 3, 4] などの 2 つのチャンクに分割できます。
  ただし、[1, 0]、[2]、[3]、[4] に分割するのが可能なチャンクの最大数です。

制約:

n == arr.length
1 0 arr のすべての要素は
• 一意です。

ヒント:

最初のチャンクは、A[:k 1] == [0, 1, 2, ...k]; となる最小の k として見つけることができます。その後、このプロセスを繰り返します。

解決策:

各チャンクを個別にソートでき、連結した結果が配列全体のソートされたバージョンになるように、形成できるチャンクの最大数を見つける必要があります。

アプローチ：

1. 主な所見:

   配列は 0 から n-1 までの整数の順列です。このアイデアは、配列を走査し、チャンクを分離できる位置を見つけることです。
   チャンク内のすべてのインデックスについて、元のソートされた配列のその時点までの最大要素がその時点以降の最小要素を超えない場合、チャンクはソートできます。

2. 戦略:

   左から右に移動するときに発生する最大値を追跡します。
   各インデックス i で、i までの最大値が i 以下であるかどうかを確認します。この条件が当てはまる場合、左側の部分は独立してソートできるため、そのインデックスで配列を分割できることを意味します。

3. 手順:

   • 実行最大値を維持しながら配列を反復処理します。
   • 現在の最大値が現在のインデックスと等しくなるたびに、チャンクを作成できます。
   • そのようなチャンクの数を数えます。

このソリューションを PHP で実装してみましょう: 769。ソートする最大チャンク

<?php
/**
 * @param Integer[] $arr
 * @return Integer
 */
function maxChunksToSorted($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$arr1 = [4, 3, 2, 1, 0];
$arr2 = [1, 0, 2, 3, 4];

echo maxChunksToSorted($arr1); // Output: 1
echo "\n";
echo maxChunksToSorted($arr2); // Output: 4
?>

説明：

1. 初期化:

   • 配列を走査するときに配列内の最大値を正しく追跡できるように、maxSoFar = -1 から開始します。
   • chunks = 0 は、形成できるチャンクの数を追跡します。

2. ループ:

   • 配列内の各要素をループします。
   • 各要素について、現在の要素と以前に確認された最大値の間の最大値になるように maxSoFar を更新します。
   • maxSoFar == i の場合、インデックス i までの配列を独立して並べ替えることができ、これが有効なチャンクであることを意味します。
   • この条件が当てはまるたびに、チャンク カウントが増加します。

3. 戻る:

   • 最後に、チャンクの総数が返されます。

時間計算量:

• 時間計算量: O(n)、n は配列の長さです。配列を通過するパスは 1 回だけです。
• 空間複雑度: O(1)。中間結果を保存するために少数の変数のみを使用しているためです。

チュートリアルの例:

arr = [1, 0, 2, 3, 4] の場合:

• インデックス 0 では、これまでに見つかった最大値は 1 です。ここで分割することはできません。
• インデックス 1 の最大値は 1 で、現在のインデックス 1 と一致するため、チャンクに分割できます。
• インデックス 2 の最大値は 2 で、インデックス 2 と一致するため、再度分割します。
• インデックス 3 の最大値は 3 で、インデックス 3 と一致するため、再度分割します。
• インデックス 4 の最大値は 4 で、インデックス 4 と一致するため、再度分割します。

したがって、この場合の出力は 4 つのチャンクに分割できるため、4 になります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。ソートする最大チャンク数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。