2779. Maximum Beauty of an Array After Applying Operation
- You are given a 0-indexed array
nums
and a non-negative integerk
. - 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]
.
- Choose an index
- 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).
Method 1
【O(nlog(n)) time | O(1) space】
package Leetcode.Array;
import java.util.Arrays;
/**
* @author zhengxingxing
* @date 2024/12/11
*/
public class MaximumBeautyOfAnArrayAfterApplyingOperation {
public static int maximumBeauty(int[] nums, int k) {
// Step 1: Sort the array to bring close numbers together.
Arrays.sort(nums);
int maxBeauty = 1; // Tracks the maximum beauty found.
int left = 0; // Left pointer of the sliding window.
// Iterate through the array with the right pointer.
for (int right = 0; right < nums.length; right++) {
// Check if the difference between nums[right] and nums[left] exceeds 2 * k.
// If it does, increment the left pointer to reduce the window size.
if (nums[right] - nums[left] > 2 * k) {
left++;
}
// Update the maximum beauty by comparing it to the current window size.
maxBeauty = Math.max(maxBeauty, right - left + 1);
}
return maxBeauty;
}
public static void main(String[] args) {
// Test case 1
int[] nums1 = {4, 6, 1, 2};
int k1 = 2;
System.out.println("Test case 1: " + maximumBeauty(nums1, k1)); // Expected: 3
// Test case 2
int[] nums2 = {1, 1, 1, 1};
int k2 = 0;
System.out.println("Test case 2: " + maximumBeauty(nums2, k2)); // Expected: 4
// Test case 3
int[] nums3 = {10, 1, 3, 5, 7};
int k3 = 1;
System.out.println("Test case 3: " + maximumBeauty(nums3, k3)); // Expected: 2
// Test case 4
int[] nums4 = {100, 101, 102, 103, 104};
int k4 = 2;
System.out.println("Test case 4: " + maximumBeauty(nums4, k4)); // Expected: 5
// Test case 5
int[] nums5 = {8, 2, 4, 6};
int k5 = 3;
System.out.println("Test case 5: " + maximumBeauty(nums5, k5)); // Expected: 4
}
}
Enjoy Reading This Article?
Here are some more articles you might like to read next: