Medium
You are given an integer array nums
and an integer k
.
The frequency of an element x
is the number of times it occurs in an array.
An array is called good if the frequency of each element in this array is less than or equal to k
.
Return the length of the longest good subarray of nums
.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good. It can be shown that there are no good subarrays with length more than 6.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good. It can be shown that there are no good subarrays with length more than 2.
Example 3:
Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray. It can be shown that there are no good subarrays with length more than 4.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= nums.length
public class Solution {
public int maxSubarrayLength(int[] nums, int k) {
int m1 = Integer.MIN_VALUE;
int m2 = Integer.MAX_VALUE;
for (int num : nums) {
m1 = Math.max(m1, num);
m2 = Math.min(m2, num);
}
int max = 0;
int[] f = new int[m1 - m2 + 1];
int l = 0;
int r = 0;
while (r < nums.length) {
f[nums[r] - m2]++;
while (count(f, nums[r] - m2) > k) {
f[nums[l] - m2]--;
l++;
}
max = Math.max(max, r - l + 1);
r++;
}
return max;
}
private int count(int[] f, int n) {
return f[n];
}
}