数组的最大美丽值

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

/*
 * Problem: Given an integer array nums and a non-negative integer k. 
 * In one operation, you can choose an index i that hasn't been chosen before and replace nums[i] with any integer in the range [nums[i] - k, nums[i] + k]. 
 * The beauty value of the array is defined as the length of the longest subsequence of equal elements. 
 * Return the maximum beauty value the array can achieve after any number of such operations.
 */

import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class SolutionStream {
    public int maximizeBeauty(int[] nums, int k) {
        Map<Integer, Long> freqMap = Arrays.stream(nums)
            .boxed()
            .flatMap(num -> Arrays.stream(new int[k * 2 + 1]).mapToObj(i -> num - k + i))
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        return freqMap.values().stream().mapToInt(Long::intValue).max().orElse(0);
    }

    public static void main(String[] args) {
        SolutionStream sol = new SolutionStream();
        int[] nums1 = {4, 6, 1, 2};
        int k1 = 2;
        System.out.println(sol.maximizeBeauty(nums1, k1)); // Output: 3

        int[] nums2 = {1, 1, 1, 1};
        int k2 = 10;
        System.out.println(sol.maximizeBeauty(nums2, k2)); // Output: 4
    }
}

这个题解使用了滑动窗口的技术。首先，创建一个数组 `cnt`，其长度为最大值 `max(nums) + 1` 或 `2*k + 1` 中的较大者，用于计数 `nums` 中每个元素的出现次数。接着，通过滑动窗口（窗口大小为 `2*k`）迭代 `cnt` 数组，窗口内的元素总和 `tot` 表示在当前的数字范围内，通过调整可以实现的元素值相同的最大数量。这个范围内的所有元素都可以调整到窗口的中间值，从而形成一个长的相同元素的子序列。随着窗口的滑动，更新结果 `ans` 为窗口内元素和的最大值，即可能的最大美丽值。

O(n + max(nums))

O(max(max(nums), 2*k))