操作適用後の配列の美しさを最大限に高める

2779。操作適用後の配列の最大の美しさ

難易度: 中

トピック: 配列、二分探索、スライディング ウィンドウ、並べ替え

0 インデックス付き 配列 nums と、非負 整数 k が与えられます。

1 回の操作で次のことができます:

• [0, nums.length - 1] の範囲から、以前に選択されていないインデックス i を選択します。
• nums[i] を [nums[i] - k, nums[i] k] の範囲の任意の整数に置き換えます。

配列の美しさは、等しい要素で構成される最長のサブシーケンスの長さです。

操作を何度でも適用した後の配列 nums の最大の美しさを返します。

各インデックスに操作を適用できるのは 1 回だけであることに注意してください。

配列の

サブシーケンス は、残りの要素の順序を変更せずに、いくつかの要素 (おそらく何もない) を削除することによって、元の配列から生成された新しい配列です。

例 1:

• 入力: nums = [4,6,1,2]、k = 2
• 出力: 3
• 説明: この例では、次の操作を適用します。
  インデックス 1 を選択し、(範囲 [4,8] から) 4 に置き換えます。数値 = [4,4,1,2]。
  インデックス 3 を選択し、(範囲 [0,4] から) 4 に置き換えます。数値 = [4,4,1,4]。
  適用された操作後の配列 nums の美しさは 3 (インデックス 0、1、および 3 で構成されるサブシーケンス) です。
  3 が達成可能な最大長であることが証明できます。

例 2:

• 入力: nums = [1,1,1,1]、k = 10
• 出力: 4
• 説明: この例では、操作を適用する必要はありません。
  配列 nums の美しさは 4 (配列全体) です。

制約:

1 5 0 5

ヒント:

配列を並べ替えます。
問題は次のようになります: A[j] - A[i] ≤ 2 * k となる最大の部分配列 A[i … j] を見つけます。

解決策:

並べ替えとスライディング ウィンドウのアプローチを利用できます。

アプローチ：

1. 配列を並べ替えます: 並べ替えにより、最大要素と最小要素の差が 2k を超えないサブシーケンスの識別が簡単になります。
2. スライディング ウィンドウ手法: 差 nums[j] - nums[i] のインデックス [i, j] を維持します。 。 i または j を調整してウィンドウ サイズを最大化します。

このソリューションを PHP で実装してみましょう: 2779。操作適用後の配列の最大の美しさ

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

// Example Usage:
$nums1 = [4, 6, 1, 2];
$k1 = 2;
echo maximumBeauty($nums1, $k1) . "\n"; // Output: 3

$nums2 = [1, 1, 1, 1];
$k2 = 10;
echo maximumBeauty($nums2, $k2) . "\n"; // Output: 4
?>

説明：

1. 配列の並べ替え:
   • 並べ替えにより、インデックス [i, j] で定義されたウィンドウにすべての要素が昇順で含まれるようになり、最小値と最大値の差を確認しやすくなります。窓。
2. スライディング ウィンドウ:
   • 先頭は i と j の両方で始めます。
   • 条件 nums[j] - nums[i] > が満たされるたびに、j をインクリメントしてウィンドウを拡張し、i をインクリメントしてウィンドウを有効に保ちます。 2k が違反されています。
   • 各ステップで、現在の有効なウィンドウのサイズ j - i 1 を計算し、maxBeauty を更新します。

---

複雑さの分析:

1. 時間計算量:
   • 配列のソート: O(n log n).
   • スライディング ウィンドウ トラバーサル: O(n).
   • 全体: O(n log n).
2. 空間の複雑さ:
   • O(1)。ソリューションでは追加の変数がいくつかしか使用されないためです。

---

例:

入力 1:

$nums = [4, 6, 1, 2];
$k = 2;
echo maximumBeauty($nums, $k); // Output: 3

入力 2:

$nums = [1, 1, 1, 1];
$k = 10;
echo maximumBeauty($nums, $k); // Output: 4

このソリューションは制約を遵守し、大きな入力の結果を効率的に計算します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が操作適用後の配列の美しさを最大限に高めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。