山配列を作成するための最小除去数

1671年。山配列を作成するための最小除去数

難易度: 難しい

トピック: 配列、二分探索、動的計画法、貪欲

次の場合に限り、配列 arr が マウンテン配列 であることを思い出してください。

• arr.length >= 3
• 0 を持つインデックス i (0-indexed
  ) が存在します。私は＜ arr.length - 1 は次のようになります。
  arr[0]
arr[i] >到着[i 1] > ... > arr[arr.length - 1]

整数配列 nums を指定すると、nums を 山配列にするために削除する要素の最小数を返します。

例 1:

• 入力: 数値 = [1,3,1]
• 出力: 0
• 説明: 配列自体はマウンテン配列であるため、要素を削除する必要はありません。

例 2:

• 入力: 数値 = [2,1,1,5,6,2,3,1]
• 出力: 3
• 説明: 1 つの解決策は、インデックス 0、1、および 5 の要素を削除して、配列 nums = [1,5,6,3,1] にすることです。

制約:

• 3
• 1 9
• num から山の配列を作成できることが保証されています。

ヒント:

1. 最小要素ではなく逆の方向を考えて、最大の山部分列を削除します
2. LIS について考えてみると、それに近いものがあります

解決策:

削除する要素を直接カウントするのではなく、最大の山の部分列を見つけるというアイデアを持つ動的プログラミング アプローチを使用できます。このアプローチは、配列内の各位置に対して 2 つの 最長増加サブシーケンス (LIS) を見つけることに基づいています。1 つは 左から右 に進み、もう 1 つは 右から右に進みます。左。可能な限り長い山のサブシーケンスが得られたら、元の配列の長さとこのサブシーケンスの長さの差により、削除する最小限の要素が得られます。

ソリューションの概要

1. 増大するサブシーケンスの長さを特定する:

   • leftLIS 配列を計算します。 ここで、leftLIS[i] は、i で終わる最長の増加サブシーケンス (左から右へ) の長さを表します。

2. 減少するサブシーケンスの長さを特定する:

   • rightLIS 配列を計算します。rightLIS[i] は、i から始まる (右から左へ) 最も長い減少サブシーケンスの長さを表します。

3. 山の最大長を計算します:

   • 各インデックス i について、0 1 および rightLIS[i] > 1)。 i での山の長さを leftLIS[i] rightLIS[i] - 1 として計算します。

4. 最小限の除去を取得します:

   • 削除する最小要素は、元の配列の長さから見つかった最長の山の長さを引いたものになります。

このソリューションを PHP で実装してみましょう: 1671。山配列を作成するための最小除去数

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

// Example usage
$nums1 = [1, 3, 1];
echo minimumMountainRemovals($nums1); // Output: 0

$nums2 = [2, 1, 1, 5, 6, 2, 3, 1];
echo minimumMountainRemovals($nums2); // Output: 3
?>

説明：

1. 左 LIS 計算:

   • leftLIS[i] には、i で終わる増加するサブシーケンスの最大長が格納されます。各 i を反復処理し、各 i について 0 から i-1 まで反復して、i で終わる最長のサブシーケンスを見つけます。

2. 正しい LIS 計算:

   • rightLIS[i] には、i から始まる減少するサブシーケンスの最大長が格納されます。 n-2 から 0 まで逆方向に反復し、各 i について n-1 から i 1 まで反復して、i から始まる最長の部分列を見つけます。

3. 山の計算:

   • インデックス i の有効なピークは leftLIS[i] > でなければなりません。 1 と右LIS[i] > 1. i を頂点とする山の長さは leftLIS[i] rightLIS[i] - 1.

4. 最終計算:

   • 必要な最小の削除は、元の配列の長さと見つかった最大の山の長さの差です。

複雑さの分析

• 時間計算量: O(n²)、LIS 計算の二重ループが原因です。
• 空間複雑度: O(n)、leftLIS 配列と rightLIS 配列を格納するため。

このソリューションにより、最大の山の部分列が見つかり、山の配列を達成するために必要な最小限の除去が計算されます。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が山配列を作成するための最小除去数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。