2779. 数组的最大美丽值

🟠   🔖  数组 二分查找 排序 滑动窗口  🔗 力扣 LeetCode

题目

You are given a 0-indexed array nums and a non-negative integer k.

In one operation, you can do the following:

• Choose an index i that hasn 't been chosen before from the range [0, nums.length - 1].
• Replace nums[i] with any integer from the range [nums[i] - k, nums[i] + k].

The beauty of the array is the length of the longest subsequence consisting of equal elements.

Return _themaximum possible beauty of the array _nums after applying the operation any number of times.

Note that you can apply the operation to each index only once.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.

Example 1:

Input: nums = [4,6,1,2], k = 2

Output: 3

Explanation: In this example, we apply the following operations:

• Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2].
• Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4].

After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3).

It can be proven that 3 is the maximum possible length we can achieve.

Example 2:

Input: nums = [1,1,1,1], k = 10

Output: 4

Explanation: In this example we don't have to apply any operations.

The beauty of the array nums is 4 (whole array).

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i], k <= 10^5

题目大意

给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。

在一步操作中，你可以执行下述指令：

• 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
• 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。

数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 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] 。

执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。

可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

示例 2：

输入： nums = [1,1,1,1], k = 10

输出： 4

解释： 在这个示例中，我们无需执行任何操作。

数组 nums 的美丽值是 4（整个数组）。

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i], k <= 10^5

解题思路

解决这个问题需要考虑如何通过操作将数组中尽可能多的元素调整到某个特定的值，使该值的频率达到最大。

由于每个元素的调整范围是有限的，问题可以转化为查找所有可能值区间中最大化重叠覆盖的值。

我们可以用一个差分数组来快速计算某一值是否被多个区间覆盖。

1. 初始化一个差分数组 count，大小为 maxValue + 1（包括所有可能的值范围）。
2. 遍历 nums，对每个 nums[i]，计算其可调整区间 [nums[i] - k, nums[i] + k]，并更新差分数组 count：
   • 在 Math.max(num - k, 0) 位置加 +1 表示区间的开始。
   • 在 Math.min(num + k + 1, maxValue) 位置减 -1 表示区间的结束。
3. 对差分数组求前缀和，得到每个值的覆盖次数，取最大值作为结果。

复杂度分析

• 时间复杂度：O(n + maxValue)；
  • 遍历 nums 更新差分数组需要 O(n)；
  • 遍历差分数组求前缀和需要 O(maxValue)；
  • 总时间复杂度为 O(n + maxValue)。
• 空间复杂度：O(maxValue)，差分数组占用 O(maxValue) 的空间。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function (nums, k) {
	if (nums.length == 1) return 1;

	const maxValue = Math.max(...nums);

	// 差分数组
	let count = new Array(maxValue + 1).fill(0);

	// 更新差分数组
	for (let num of nums) {
		const start = Math.max(num - k, 0),
			end = Math.min(num + k + 1, maxValue);
		count[start]++;
		count[end]--;
	}

	// 计算前缀和，找到最大覆盖次数
	let curSum = 0;
	let maxBeauty = 0;
	for (let val of count) {
		curSum += val;
		maxBeauty = Math.max(maxBeauty, curSum);
	}

	return maxBeauty;
};

相关题目

题号	标题	题解	标签	难度	力扣
325	和等于 k 的最长子数组长度 🔒		数组 哈希表 前缀和	🟠	🀄️ 🔗
2294	划分数组使最大差为 K		贪心 数组 排序	🟠	🀄️ 🔗