数组的最大美丽值

标签: 数组 二分查找 排序 滑动窗口

难度: Medium

给你一个下标从 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 <= 105
  • 0 <= nums[i], k <= 105

Submission

运行时间: 210 ms

内存: 28.4 MB

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        cnt = [0] * max(max(nums) + 1, 2 * k + 1)
        for num in nums:
            cnt[num] += 1
        left = 0
        tot = 0
        ans = 0
        for right in range(len(cnt)):
            tot += cnt[right]
            if right >= 2 * k:
                ans = max(ans, tot)
                tot -= cnt[left]
                left += 1
        return ans

Explain

这个题解使用了滑动窗口的技术。首先，创建一个数组 `cnt`，其长度为最大值 `max(nums) + 1` 或 `2*k + 1` 中的较大者，用于计数 `nums` 中每个元素的出现次数。接着，通过滑动窗口（窗口大小为 `2*k`）迭代 `cnt` 数组，窗口内的元素总和 `tot` 表示在当前的数字范围内，通过调整可以实现的元素值相同的最大数量。这个范围内的所有元素都可以调整到窗口的中间值，从而形成一个长的相同元素的子序列。随着窗口的滑动，更新结果 `ans` 为窗口内元素和的最大值，即可能的最大美丽值。

时间复杂度: O(n + max(nums))

空间复杂度: O(max(max(nums), 2*k))

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        # 初始化计数数组，长度为max(nums)+1或2*k+1中的最大值
        cnt = [0] * max(max(nums) + 1, 2 * k + 1)
        # 统计nums中每个元素的出现次数
        for num in nums:
            cnt[num] += 1
        # 初始化滑动窗口的左边界和窗口内元素总数
        left = 0
        tot = 0
        # 初始化最大美丽值
        ans = 0
        # 遍历计数数组，使用滑动窗口计算可能的最大美丽值
        for right in range(len(cnt)):
            tot += cnt[right]
            # 窗口大小超过2*k时，移动窗口
            if right >= 2 * k:
                ans = max(ans, tot)
                tot -= cnt[left]
                left += 1
        return ans

Explore

选择`max(max(nums) + 1, 2 * k + 1)`作为计数数组`cnt`的长度是为了确保数组可以包含`nums`中所有可能的元素值，同时也能够满足最大可能的调整范围，即`2*k`。这样可以确保所有元素都能在数组`cnt`中被统计，无论它们的值是多少，只要它们在`nums`的最大值和`2*k`的范围内。

在这个算法中，中间值并没有直接指定，而是隐含地表示为窗口中心的值，即窗口的平均值或者中点位置的元素值。因为窗口保持恒定的大小`2*k`，所以窗口的`中间值`可以认为是窗口起始值加上`k`。这个值是理论上最佳的调整目标，因为在它的±k范围内的所有值都可以调整到这个中间值。

当`right`指针超过`2*k`时，意味着窗口已经超出了其最大允许的大小`2*k`。为了维持窗口大小不变，我们需要将`left`指针向右移动，这样可以确保窗口的大小恒定为`2*k`。这种移动是为了继续探索其他潜在的子数组，同时确保窗口的滑动不会超出数组`cnt`的边界。

理论上，窗口内通过调整可以实现的元素值相同的最大数量是基于假设窗口内的所有元素都可以调整到`中间值`。然而，在实际情况中，这种调整只有在元素的原始值与目标值的差值不超过`k`时才是可行的。因此，虽然`tot`给出了理论上的最大可能数量，但实际上能否达到这个数量还取决于窗口内元素值的具体分布和调整的范围`k`。