配列をソートするために削除される最短のサブ配列

1574年。配列をソートするために削除される最短のサブ配列

難易度: 中

トピック: 配列、2 ポインター、二分探索、スタック、単調スタック

整数配列 arr が与えられた場合、arr 内の残りの要素が 非減少になるように、arr から部分配列 (空でもよい) を削除します。

削除する最短の部分配列の長さを返します。

サブ配列は、配列の連続したサブシーケンスです。

例 1:

• 入力: arr = [1,2,3,10,4,2,3,5]
• 出力: 3
• 説明: 削除できる最も短い部分配列は、長さ 3 の [10,4,2] です。その後の残りの要素は、ソートされた [1,2,3,3,5] になります。
  • もう 1 つの正しい解決策は、サブ配列 [3,10,4] を削除することです。

例 2:

• 入力: arr = [5,4,3,2,1]
• 出力: 4
• 説明: 配列は厳密に減少しているため、保持できる要素は 1 つだけです。したがって、長さ 4 の部分配列 [5,4,3,2] または [4,3,2,1] を削除する必要があります。

例 3:

• 入力: arr = [1,2,3]
• 出力: 0
• 説明: 配列はすでに非減少です。要素を削除する必要はありません。

制約:

• 1 5
• 0 9

ヒント:

1. 重要なのは、それぞれ最初の要素で始まるか、最後の要素で終わる最長の非減少部分配列を見つけることです。
2. 一部の部分配列を削除すると、結果はソートされたプレフィックスとソートされたサフィックスの連結になります。ここで、プレフィックスの最後の要素はサフィックスの最初の要素よりも小さくなります。

解決策:

並べ替えと二分探索手法を使用できます。計画は次のとおりです:

アプローチ：

1. 2 つの指針がアプローチします:

   • まず、最長の非減少プレフィックス (左ポインター) を特定します。
   • 次に、最長の非減少接尾辞 (右ポインター) を特定します。
   • その後、配列の中央部分を考慮し、結合された配列が減少しないように削除する部分配列を調整して、これら 2 つの部分配列を結合してみます。

2. 単調スタック:

   • 単調スタックを使用すると、ソートされた方法で部分配列要素を管理できます。

3. 手順:

   • 最長の非減少プレフィックス (左) を見つけます。
   • 最長の非減少接尾辞 (右) を見つけます。
   • 有効な組み合わせを形成できる要素を探して、2 つの部分配列をマージしてみます。

4. 最適化:

   • 二分探索を使用して、削除する最小の部分配列を見つけるためのマージ ステップを最適化します。

このソリューションを PHP で実装してみましょう: 1574。配列をソートするために削除される最短のサブ配列

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

// Test cases
echo shortestSubarrayToRemove([1, 2, 3, 10, 4, 2, 3, 5]) . "\n"; // Output: 3
echo shortestSubarrayToRemove([5, 4, 3, 2, 1]) . "\n";           // Output: 4
echo shortestSubarrayToRemove([1, 2, 3]) . "\n";                 // Output: 0
?>

説明：

1. 最長の減少しないプレフィックスとサフィックス:

   • プレフィックスは、要素が非降順になるまで配列を最初から走査することによって決定されます。
   • 同様に、接尾辞は末尾からのトラバースによって決定されます。

2. 初期最小削除:

   • プレフィックスまたはサフィックスのみを保持して、削除の長さを計算します。

3. プレフィックスとサフィックスのマージ:

   • 2 つのポインター (接頭辞の i と接尾辞の j) を使用して、接頭辞の最後の要素が接尾辞の最初の要素以下になるように削除する最小の部分配列を見つけます。

4. 結果を返す:

   • 結果は、最初の削除またはプレフィックスとサフィックスのマージの小さい方として計算された、削除するサブ配列の最小長です。

複雑

• 時間計算量: O(n)、配列は最大 2 回走査されるため。
• 空間複雑度: O(1)、少数の変数のみが使用されるため。

このソリューションは、2 ポインター手法を使用して配列をソートするために削除する最短の部分配列を効率的に見つけ、10^5 要素の制約までの大きな配列を処理します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が配列をソートするために削除される最短のサブ配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。