力扣每日一题 6/15 滑动窗口

2779.数组的最大美丽值【中等】

题目：

给你一个下标从 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

分析问题：

       首先看到这个问题的第一反应，就是模拟它的寻找过程，创建一个字典，去走一遍循环把能改变成 [nums[i] - k, nums[i] + k] 的值全部都放入字典里面，并且对其进行计数，然后输出计数最多的数即可，但是代码实现过后，时间超出限制，具体代码如下：

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        dic={}
        n=len(nums)
        for i in range(n):
            for j in range(nums[i]-k,nums[i]+k+1):
                if j not in dic:
                    dic[j]=1
                else: dic[j]+=1
        x=0
        for q in dic.values():
            if q>x: x=q
        return x

提交结果如下图：

时间超限。然后借鉴了题解区灵神的思路，他运用的正是 滑动窗口 的思路。 即首先分析子序列的顺序不受影响，所以把原数组nums进行排序(假设从小到大排)，把原数组的每一个数值x都看作是

[x - k, x+ k] 这样的一个区间。排序后，选出的区间是连续的，我们只需考虑最左边的区间 [x−k,x+k]和最右边的区间 [y−k,y+k]，如果这两个区间的交集不为空，那么选出的这些区间的交集不为空。也就是说，要满足 x+k≥y−k，即 y−x≤2k。

于是原问题等价于：

• 排序后，找最长的连续子数组，其最大值减最小值不超过 2k。

 只要子数组满足这个要求，对应的区间的交集就不为空，也就是子数组的元素都可以变成同一个数。然后枚举nums中的元素，判断其区间长度，取最大值即可。

代码实现：

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        nums.sort()
        left,ans=0,0
        for right,x in enumerate(nums):
            while x-nums[left] > 2*k:
                left+=1
            ans=max(ans,right-left+1)
        return ans

总结：

以下是对代码的详细解释：

       首先，对输入的列表 `nums` 进行排序。

       然后，使用两个指针 `left` 和 `right` 遍历列表。`left` 指针从起始位置开始，`right` 指针依次遍历列表中的每个元素 `x`。 在每次循环中，通过一个 `while` 循环检查当前元素 `x` 与 `left` 指针所指元素的差值是否大于 `2*k` 。如果是，就将 `left` 指针向右移动一位。 接着，计算当前窗口（`right - left + 1`）的长度，并更新最大窗口长度 `ans` 。

       最后，方法返回最大窗口长度 `ans` 作为结果。

这道题主要考查了以下几个方面：

1. 对数组的排序操作。通过对 nums 进行排序，为后续的双指针操作奠定基础，这考查了对基本排序算法的理解和运用。
2. 双指针算法。使用 left 和 right 两个指针来遍历数组，有效地计算满足特定条件的窗口大小，这考验了对指针移动逻辑和条件判断的掌握。
3. 数学推理和逻辑思维。在判断元素差值是否超过 2*k 时，需要清晰的数学推理和逻辑思考。

通过这道题，可以学到：

1. 熟练掌握排序算法的应用场景，以便为后续的处理提供便利。
2. 深入理解双指针算法的精髓，如何通过合理移动指针来解决问题，提高算法效率。
3. 增强数学推理和逻辑判断能力，能够准确地分析问题中的条件和约束。

反思方面：

1. 在解决类似问题时，要首先思考是否可以通过排序来简化问题。
2. 对于双指针的移动条件，需要仔细分析，确保不会遗漏边界情况或出现错误的判断。
3. 不断练习类似的数学推理和逻辑判断，提高解决复杂条件问题的能力。

“妄想进入虚空，却被虚空吞噬。” ——《DreamStars》