2779。應(yīng)用操作后數(shù)組的最大美感

難度：中等

主題：數(shù)組、二分查找、滑動(dòng)窗口、排序

給你一個(gè)0索引數(shù)組nums和一個(gè)非負(fù)整數(shù)k。

在一次操作中，您可以執(zhí)行以下操作：

• 從 [0, nums.length - 1] 范圍中選擇 之前未選擇過的索引 i。
• 將 nums[i] 替換為 [nums[i] - k, nums[i] k] 范圍內(nèi)的任意整數(shù)。

數(shù)組的beauty是由相等元素組成的最長子序列的長度。

返回應(yīng)用操作任意次數(shù)后最大數(shù)組nums可能的美度。

注意您只能對(duì)每個(gè)索引應(yīng)用一次操作。

數(shù)組的子序列是通過刪除原始數(shù)組中的一些元素（可能沒有）而不改變剩余元素的順序而生成的新數(shù)組。

示例1：

• 輸入： nums = [4,6,1,2], k = 2
• 輸出： 3
• 說明： 在此示例中，我們應(yīng)用以下操作：
  • 選擇索引 1，將其替換為 4（范圍 [4,8]），nums = [4,4,1,2]。
  • 選擇索引 3，將其替換為 4（范圍 [0,4]），nums = [4,4,1,4]。
  • 應(yīng)用操作后，數(shù)組 nums 的美度為 3（由索引 0、1 和 3 組成的子序列）。
  • 可以證明3是我們可以達(dá)到的最大可能長度。

示例2：

• 輸入： nums = [1,1,1,1], k = 10
• 輸出： 4
• 說明：在此示例中，我們不必應(yīng)用任何操作。
  • 數(shù)組 nums 的美麗值為 4（整個(gè)數(shù)組）。

約束：

• 1 5
• 0 5

提示：

1. 對(duì)數(shù)組進(jìn)行排序。
2. 問題變?yōu)椋赫业阶畲笞訑?shù)組 A[i … j]，使得 A[j] - A[i] ≤ 2 * k。

解決方案：

我們可以利用排序和滑動(dòng)窗口方法。

方法：

1. 對(duì)數(shù)組進(jìn)行排序：排序簡化了識(shí)別最大元素和最小元素之間的差異不超過2k.
的子序列
2. 滑動(dòng)窗口技術(shù)：維護(hù)索引窗口[i, j]，其中差異nums[j] - nums[i] 。調(diào)整 i 或 j 以使窗口大小最大化。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：2779。應(yīng)用操作后數(shù)組的最大美感

<?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. 對(duì)數(shù)組進(jìn)行排序：
   • 排序確保由索引 [i, j] 定義的窗口中的所有元素均按升序排列，這使得更容易檢查中的最小值和最大值之間的差異窗戶。
2. 滑動(dòng)窗口：
   • 以 i 和 j 開頭。
   • 通過增加 j 來擴(kuò)展窗口，并在條件 nums[j] - nums[i] > 時(shí)通過增加 i 來保持窗口有效。 2k 被侵犯。
   • 每一步計(jì)算當(dāng)前有效窗口的大小j - i 1并更新maxBeauty。

---

復(fù)雜度分析：

1. 時(shí)間復(fù)雜度：
   • 對(duì)數(shù)組進(jìn)行排序：O(n log n).
   • 滑動(dòng)窗口遍歷：O(n).
   • 總體：O(n log n).
2. 空間復(fù)雜度：
   • O(1)，因?yàn)樵摻鉀Q方案僅使用幾個(gè)附加變量。

---

示例：

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

該解決方案遵守約束并有效計(jì)算大量輸入的結(jié)果。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是應(yīng)用運(yùn)算后數(shù)組的最大美感的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！