class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
}
};
6929. 数组的最大美丽值
给你一个下标从 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原站题解
python3 解法, 执行用时: 373 ms, 内存消耗: 27.5 MB, 提交时间: 2024-06-15 10:04:23
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
m = max(nums)
diff = [0] * (m + 2)
for x in nums:
diff[max(x - k, 0)] += 1
diff[min(x + k + 1, m + 1)] -= 1
res, count = 0, 0
for x in diff:
count += x
res = max(res, count)
return res
golang 解法, 执行用时: 102 ms, 内存消耗: 8.4 MB, 提交时间: 2024-06-15 10:04:09
func maximumBeauty(nums []int, k int) int {
m := 0
for _, x := range nums {
m = max(m, x)
}
diff := make([]int, m + 2)
for _, x := range nums {
diff[max(x - k, 0)]++
diff[min(x + k + 1, m + 1)]--
}
res, count := 0, 0
for _, x := range diff {
count += x
res = max(res, count)
}
return res
}
rust 解法, 执行用时: 14 ms, 内存消耗: 3.3 MB, 提交时间: 2024-06-15 10:03:50
impl Solution {
pub fn maximum_beauty(nums: Vec<i32>, k: i32) -> i32 {
let mut m = nums.iter().max().unwrap();
let mut diff = vec![0; (m + 2) as usize];
for x in nums.iter() {
diff[std::cmp::max(x - k, 0) as usize] += 1;
diff[std::cmp::min(x + k + 1, m + 1) as usize] -= 1;
}
let mut res = 0;
let mut count = 0;
for x in diff.iter() {
count += x;
res = std::cmp::max(res, count);
}
res as i32
}
}
rust 解法, 执行用时: 47 ms, 内存消耗: 3.4 MB, 提交时间: 2024-06-15 10:03:36
impl Solution {
pub fn maximum_beauty(nums: Vec<i32>, k: i32) -> i32 {
let mut nums = nums.clone();
nums.sort();
let mut res = 0;
let mut i = 0;
let mut j = 0;
while i < nums.len() {
while nums[i] - 2 * k > nums[j] {
j += 1;
}
res = std::cmp::max(res, i - j + 1);
i += 1;
}
res as i32
}
}
javascript 解法, 执行用时: 254 ms, 内存消耗: 63.8 MB, 提交时间: 2024-06-15 10:03:21
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumBeauty = function(nums, k) {
let res = 0, n = nums.length;
nums.sort((x, y) => x - y);
for (let i = 0, j = 0; i < n; i++) {
while (nums[i] - 2 * k > nums[j]) {
j++;
}
res = Math.max(res, i - j + 1);
}
return res;
};
python3 解法, 执行用时: 384 ms, 内存消耗: 27.6 MB, 提交时间: 2023-07-17 11:03:56
'''
排序+双指针
由于选的是子序列，且子序列的元素都相等，所以元素顺序对答案没有影响，可以先对数组排序。
由于替换操作替换的是一个连续范围内的数，所以排序后，选出的子序列必然也是一段连续子数组。
那么问题变成：「找最长的连续子数组，其最大值减最小值不超过 2k」，
只要子数组满足这个要求，其中的元素都可以变成同一个数。
'''
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
ans = left = 0
for right, x in enumerate(nums):
while x - nums[left] > k * 2:
left += 1
ans = max(ans, right - left + 1)
return ans
cpp 解法, 执行用时: 180 ms, 内存消耗: 98.3 MB, 提交时间: 2023-07-17 11:02:52
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
int ans = 0, n = nums.size();
sort(nums.begin(), nums.end());
for(int l = 0, r = 0; r < n; ++r) {
while(nums[l] < nums[r] - 2 * k) ++l;
ans = max(ans, r - l + 1);
}
return ans;
}
};
java 解法, 执行用时: 47 ms, 内存消耗: 54.2 MB, 提交时间: 2023-07-17 11:02:35
class Solution {
public int maximumBeauty(int[] nums, int k) {
Arrays.sort(nums);
int ans = 0, n = nums.length;
for (int l = 0, r = 0; r < n; ++r) {
while (nums[r] > nums[l] + 2 * k) l++;
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}
golang 解法, 执行用时: 236 ms, 内存消耗: 8.8 MB, 提交时间: 2023-07-17 11:02:03
func maximumBeauty(nums []int, k int) (ans int) {
sort.Ints(nums)
left := 0
for right, x := range nums {
for x-nums[left] > k*2 {
left++
}
ans = max(ans, right-left+1)
}
return
}
func max(a, b int) int { if b > a { return b }; return a }