题目：
给你一个下标从 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 <= 1050 <= nums[i], k <= 105
暴力破解法
思路：
从题目上来看，原数组元素的顺序其实是没有什么关系的，反正我最后要求的是子序列
其次，对于每个数组元素，我们会将其变成一个区间，最后要求的就是有重叠区域的最大区间数目。
所以我们可以对数组元素进行排序，这样我们从l = q[0][0]所有区间的最左元素 到r = q[n - 1][1]所有区间的最右元素，这个数字依次判断，找到数字能落在的最多区间数，就是答案
代码：
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> q(n);
for (int i = 0; i < n; i++) {
vector<int> now(2);
now[0] = nums[i] - k;
now[1] = nums[i] + k;
q[i] = now;
}
int l = q[0][0], r = q[n - 1][1];
int ans = 0;
for (int i = l; i <= r; i++) {
int cur = 0;
for (int j = 0; j < n; j++) {
if (i < q[j][0]) {
break;
}else if (i >= q[j][0] && i <= q[j][1]) {
cur++;
}
}
ans = max(ans, cur);
}
return ans;
}
};
时间复杂度：O(n^2)
铁超时了，空间复杂度也大
滑动串口优化法
思路：
由于选的是子序列，且操作后子序列的元素都相等，所以元素顺序对答案没有影响，可以先对数组排序。
示例 1 排序后 nums=[1,2,4,6]。由于每个数 xxx 可以改成闭区间 [x−k,x+k] 中的数，我们把示例 1 的每个数看成闭区间，也就是
题目要求的「由相等元素组成的最长子序列」，相当于选出若干闭区间，这些区间的交集不为空。
排序后，选出的区间是连续的，我们只需考虑最左边的区间 [x−k,x+k] 和最右边的区间 [y−k,y+k]，如果这两个区间的交集不为空，那么选出的这些区间的交集不为空。也就是说，要满足 x+k ≥ y−k 即 y−x ≤ 2k
于是原问题等价于：排序后，找最长的连续子数组，其最大值减最小值不超过 2k。
只要子数组满足这个要求，对应的区间的交集就不为空，也就是子数组的元素都可以变成同一个数。
这可以用 滑动窗口 解决。枚举 nums[right] 作为子数组的最后一个数，一旦 nums[right]−nums[left] > 2k，就移动左端点 left。
左端点停止移动时，下标在 [left,right] 的子数组就是满足要求的子数组，用子数组长度 right−left+1 更新答案的最大值。
时间复杂度：O(nlogn)，其中 n 为 nums 的长度。瓶颈在排序上。虽然写了个二重循环，但是内层循环中对 left 加一的总执行次数不会超过 n 次，所以滑窗那部分的时间复杂度为 O(n)。
空间复杂度：O(1)。忽略排序的栈开销，仅用到若干额外变量。
代码：
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
ranges::sort(nums);
int ans = 0, left = 0;
for (int right = 0; right < nums.size(); right++) {
while (nums[right] - nums[left] > k * 2) {
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
最精彩的部分就是枚举右端点而不是左端点，这样就保证了内层for循环的次数不超过n次，直接将复杂度压缩到O(n).