应用运算后数组的最大美感

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中文网其他相关文章！