数组的最大美丽值
给你一个下标从 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路1
见代码注释，比较绕，但是代码量并不是特别大。
code
class Solution {
public:
//相等元素的子序列长度越长越好
//nums中的相同元素越多越好
//如何经过操作将数组中的相同元素尽可能多
//每个数都可以是加减k内的任意值
//每个位置都是一个区间
//求重叠的最大数目
//怎么求
//记录每个区间中元素的数目
//最后选取最多的那个即可
//怎么记录区间的数目
//k 1e5 不能一个个加
//区间更新
//记录数目的数组的差分
// d0 = a0
// d1 = a1 - a0
// d2 = a2 - a1
// d3 = a3 - a2
// 给[1,2]加上1，只需要d1 + 1,d3 - 1
// 需要处理边界问题，第一个元素最好为0
// 初始化就是全零，然后不断区间更新
static const int N = 300010;
int cnt_d[N];
void update(int l,int r)
{
cnt_d[l] +=1;
cnt_d[r+1] -=1;
}
int maximumBeauty(vector<int>& nums, int k) {
//cnt_d[0] = 0处理边界条件
//1 -> -1e5
//2 -> -1e5 + 1
//依次类推
for(int i = 0;i < nums.size();i ++)
{
int l = nums[i] -k + 1e5 + 1;
int r = nums[i] +k + 1e5 + 1;
//cout<<l<<" "<<r<<endl;
update(l,r);
}
//for(int i = 100000 -1;i <= 100009;i ++) cout<<cnt_d[i]<<endl;
//统计数目
for(int i = 1;i < N;i ++)
cnt_d[i] = cnt_d[i] + cnt_d[i-1];
int ans = 0;
for(int i = 1;i < N;i ++) ans = max(ans,cnt_d[i]);
return ans;
}
};