應用運算後數組的最大美感

2779。應用操作後數組的最大美感

難度：中

主題：陣列、二分查找、滑動視窗、排序

給你一個0索引數組nums和一個非負整數k。

在一次操作中，您可以執行以下操作：

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

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

回傳應用操作任意次數後最大陣列nums可能的美度。

注意您只能對每個索引套用一次操作。

數組的子序列是透過刪除原始數組中的一些元素（可能沒有）而不改變剩餘元素的順序而產生的新數組。

範例1：

• 輸入： nums = [4,6,1,2], k = 2
• 輸出： 3
• 說明： 在此範例中，我們應用以下操作：
  • 選擇索引 1，將其替換為 4（範圍 [4,8]），nums = [4,4,1,2]。
  • 選擇索引 3，將其替換為 4（範圍 [0,4]），nums = [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

提示：

1. 對陣列進行排序。
2. 問題變成：找出最大子數組 A[i … j]，使得 A[j] - A[i] ≤ 2 * k。

解：

我們可以利用排序和滑動視窗方法。

方法：

1. 對陣列進行排序：排序簡化了識別最大元素和最小元素之間的差異不超過2k.
的子序列
2. 滑動視窗技術：維護索引視窗[i, j]，其中差異nums[j] - nums[i] 。調整 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 開頭。
   • 透過增加 j 來擴展窗口，並在條件 nums[j] - nums[i] > 時透過增加 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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是應用運算後數組的最大美感的詳細內容。更多資訊請關注PHP中文網其他相關文章！