Question

2779. Maximum Beauty of an Array After Applying Operation

中文文档

Description

You are given a 0-indexed array nums and a non-negative integer k.

In one operation, you can do the following:

• Choose an index i that hasn't been chosen before from the range [0, nums.length - 1].
• Replace nums[i] with any integer from the range [nums[i] - k, nums[i] + k].

The beauty of the array is the length of the longest subsequence consisting of equal elements.

Return _the maximum possible beauty of the array _nums_ after applying the operation any number of times._

Note that you can apply the operation to each index only once.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.

 

Example 1:

Input: nums = [4,6,1,2], k = 2
Output: 3
Explanation: In this example, we apply the following operations:
- Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2].
- Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4].
After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3).
It can be proven that 3 is the maximum possible length we can achieve.

Example 2:

Input: nums = [1,1,1,1], k = 10
Output: 4
Explanation: In this example we don't have to apply any operations.
The beauty of the array nums is 4 (whole array).

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i], k <= 105

Solutions

Solution 1

class Solution:
  def maximumBeauty(self, nums: List[int], k: int) -> int:
    m = max(nums) + k * 2 + 2
    d = [0] * m
    for x in nums:
      d[x] += 1
      d[x + k * 2 + 1] -= 1
    ans = s = 0
    for x in d:
      s += x
      ans = max(ans, s)
    return ans

class Solution {
  public int maximumBeauty(int[] nums, int k) {
    int m = Arrays.stream(nums).max().getAsInt() + k * 2 + 2;
    int[] d = new int[m];
    for (int x : nums) {
      d[x]++;
      d[x + k * 2 + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      ans = Math.max(ans, s);
    }
    return ans;
  }
}

class Solution {
public:
  int maximumBeauty(vector<int>& nums, int k) {
    int m = *max_element(nums.begin(), nums.end()) + k * 2 + 2;
    vector<int> d(m);
    for (int x : nums) {
      d[x]++;
      d[x + k * 2 + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      ans = max(ans, s);
    }
    return ans;
  }
};

func maximumBeauty(nums []int, k int) (ans int) {
  m := slices.Max(nums)
  m += k*2 + 2
  d := make([]int, m)
  for _, x := range nums {
    d[x]++
    d[x+k*2+1]--
  }
  s := 0
  for _, x := range d {
    s += x
    if ans < s {
      ans = s
    }
  }
  return
}

function maximumBeauty(nums: number[], k: number): number {
  const m = Math.max(...nums) + k * 2 + 2;
  const d: number[] = new Array(m).fill(0);
  for (const x of nums) {
    d[x]++;
    d[x + k * 2 + 1]--;
  }
  let ans = 0;
  let s = 0;
  for (const x of d) {
    s += x;
    ans = Math.max(ans, s);
  }
  return ans;
}