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]。
应用操作后，数组 nums 的美丽值为 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

解题思路

这道题的关键洞察是：如果两个数字经过操作后能够变成相同的值，那么它们的差值不能超过 2*k。

核心思路分析：

假设有两个数字 a 和 b，如果它们都能变成某个相同的值 x：

  • a 能变成 x，意味着 x 在 [a-k, a+k] 范围内
  • b 能变成 x，意味着 x 在 [b-k, b+k] 范围内
  • 两个范围有交集的条件是：|a-b| ≤ 2*k

因此，问题转化为：在排序后的数组中，找到最长的子数组，使得子数组的最大值与最小值之差不超过 2*k。

解法分析：

  1. 排序 + 滑动窗口（推荐）：先排序，然后用双指针维护一个满足条件的窗口，窗口内的所有元素都能变成同一个值。

  2. 二分查找：对于每个起始位置，二分查找最远能到达的位置。

  3. 差分数组：将每个数字的操作范围 [nums[i]-k, nums[i]+k] 看作区间，统计重叠最多的位置。

滑动窗口解法最直观且高效，时间复杂度为 O(n log n)，主要消耗在排序上。

代码实现

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        int left = 0, maxBeauty = 1;
        
        for (int right = 0; right < nums.size(); right++) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            maxBeauty = max(maxBeauty, right - left + 1);
        }
        
        return maxBeauty;
    }
};

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

public class Solution {
    public int MaximumBeauty(int[] nums, int k) {
        Array.Sort(nums);
        
        int left = 0;
        int maxBeauty = 1;
        
        for (int right = 0; right < nums.Length; right++) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            maxBeauty = Math.Max(maxBeauty, right - left + 1);
        }
        
        return maxBeauty;
    }
}

var maximumBeauty = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    let left = 0;
    let maxBeauty = 1;
    
    for (let right = 0; right < nums.length; right++) {
        while (nums[right] - nums[left] > 2 * k) {
            left++;
        }
        maxBeauty = Math.max(maxBeauty, right - left + 1);
    }
    
    return maxBeauty;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，滑动窗口遍历需要 O(n)
空间复杂度O(1)只使用常数额外空间（排序为原地排序）

相关题目