题目
给你一个下标从 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$
审题
美丽值 数组中相等子元素的最长序列长度。
对每个位置的元素执行操作：
- 选择一个没有选过的
- 在制定范围内进行替换值，使得数组的众数数量增加。
双指针+动态扩张滑动窗口
- 排序数组
- 初始化滑动窗口左右指针
- 初始化最大最美子数组的长度
- 循环
while l <= r- 循环
r < n && 窗口左边值 + 2*k >= 窗口右边值- 窗口右侧左移动
- 更新最美子数组的长度
- 窗口左侧左移动
- 循环
- 返回子数组的长度
class Solution {
public int maximumBeauty(int[] nums, int k) {
Arrays.sort(nums);
int l = 0;
int r = 1;
int maxLen = 0;
while (l <= r) {
// 避免越界
while (r < nums.length && nums[l] + 2 * k >= nums[r]) {
r++;
}
maxLen = Math.max(maxLen, r - l);
l++;
}
return maxLen;
}
}
排序 + 二分查找
我们先排序，然后二分查找一下[0,2 * k = 1]区间最值。
class Solution {
public int maximumBeauty(int[] nums, int k) {
int n = nums.length;
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < n; i++) {
int r = lower_bound(nums, nums[i] + 2 * k + 1) - 1;
res = Math.max(res, r - i + 1);
}
return res;
}
// 向下的target下标二分检索
public int lower_bound(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = (l + r) >> 1;
if (nums[m] < target)
l = m + 1;
else
r = m - 1;
}
return r + 1;
}
}
以下下是一些高级算法的应用：
来自：柠檬茶山艾府的题解
差分思想，统计区间值频率
其实不一定需要排序，我们可以统计区间频率即可：
- 先遍历处最大值
- 初始化一个差分数组，长度时最大值+2
- 遍历数组，针对每一个元素：
- 统计
x - k，0较大值的频率。x - k表示x可以到达的最小值 - 降低
x + k + 1，m + 1较小值的频率。x + k + 1表示x不可以到达的最大值，避免多余累加。
- 统计
- 初始化最美子序列 res
- 初始化当前重复计数count
- 遍历频率数组
- 更新
count = count + x - 更新
res = max(res, count)
- 更新
左侧统计频率，右侧统计
class Solution {
public int maximumBeauty(int[] nums, int k) {
int m = 0;
for (int x : nums) {
m = Math.max(m, x);
}
int[] diff = new int[m + 2];
for (int x : nums) {
diff[Math.max(x - k, 0)]++;
diff[Math.min(x + k + 1, m + 1)]--;
}
int res = 0, count = 0;
for (int x : diff) {
count += x;
res = Math.max(res, count);
}
return res;
}
}
线段树
能用差分的题目线段树当然也可以使用。下面给出动态开点懒标记的线段树代码。
class Solution {
public int maximumBeauty(int[] nums, int k) {
SegmentTree root = new SegmentTree(-((int)1e5 + 5), (int)1e5 + 5);
for (int i = 0; i < nums.length; i++) {
root.update(nums[i] - k, nums[i] + k, 1);
}
return root.val;
}
}
class SegmentTree {
int val; // 区间最大值
int lazy; // 懒标记
int l; // 区间左端点
int r; // 区间右端点
SegmentTree left;// 左子树
SegmentTree right;// 右子树
// 构造函数，初始化左右区间
public SegmentTree(int l, int r) {
this.val = 0;
this.lazy = 0;
this.l = l;
this.r = r;
this.left = null;
this.right = null;
}
// 更新线段树
public void update(int tl, int tr, int d) {
if (tl <= l && r <= tr) {
val += d;
lazy += d;
return;
}
if (r < tl || tr < l) {
return;
}
pushDown();
int m = (l + r) >> 1;
// 递归更新左右子树
left.update(tl, tr, d);
right.update(tl, tr, d);
// 更新最大值
val = Math.max(val, Math.max(left.val, right.val));
}
// 二分扩展子树：[l,m] [m + 1, r]
public void pushDown() {
int m = (l + r) >> 1;
if (left == null) {
left = new SegmentTree(l, m);
}
if (right == null) {
right = new SegmentTree(m + 1, r);
}
left.val += lazy;
right.val += lazy;
left.lazy += lazy;
right.lazy += lazy;
lazy = 0;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
