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

難易度: 中

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

0 インデックス付き 配列 nums と、非負(fù) 整數(shù) k が與えられます。

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

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

配列の美しさは、等しい要素で構(gòu)成される最長(zhǎng)のサブシーケンスの長(zhǎng)さです。

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

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

配列の

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

例 1:

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

例 2:

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

制約:

1 5 0 5

ヒント:

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

解決策:

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

アプローチ：

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

このソリューションを 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] で定義されたウィンドウにすべての要素が昇順で含まれるようになり、最小値と最大値の差を確認(rèn)しやすくなります。窓。
2. スライディング ウィンドウ:
   • 先頭は i と j の両方で始めます。
   • 條件 nums[j] - nums[i] > が満たされるたびに、j をインクリメントしてウィンドウを拡張し、i をインクリメントしてウィンドウを有効に保ちます。 2k が違反されています。
   • 各ステップで、現(xiàn)在の有効なウィンドウのサイズ j - i 1 を計(jì)算し、maxBeauty を更新します。

---

複雑さの分析:

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

---

例:

入力 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

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

連絡(luò)先リンク

このシリーズが役立つと思われた場(chǎng)合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場(chǎng)合は、お?dú)葺Xにフォローしてください:

• LinkedIn
• GitHub

以上が操作適用後の配列の美しさを最大限に高めるの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。