跳转至

2958. 最多 K 个重复元素的最长子数组

来源第 119 场双周赛 Q3难度中等分数1535

题目描述

给你一个整数数组 nums 和一个整数 k 。

一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。

如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。

请你返回 nums 中 最长好 子数组的长度。

子数组 指的是一个数组中一段连续非空的元素序列。

 

示例 1：

输入：nums = [1,2,3,1,2,3,1,2], k = 2
输出：6
解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。
最长好子数组的长度为 6 。

示例 2：

输入：nums = [1,2,1,2,1,2,1,2], k = 1
输出：2
解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
最长好子数组的长度为 2 。

示例 3：

输入：nums = [5,5,5,5,5,5,5], k = 4
输出：4
解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
最长好子数组的长度为 4 。

 

提示：

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

解法

方法一：双指针

思考

求每个值出现次数均 \(\le k\) 的最长子数组。\(n \le 10^5\)，不能枚举端点。频率约束对右端单调：右端右移只可能违约，左端右移只可能修复。

哈希表计数，右指针纳入 \(x\) 后若 \(cnt[x]>k\) 则收缩左端。窗口合法时更新长度。

我们可以用两个指针 \(l\) 和 \(r\) 分别表示子数组的左右端点，初始时两个指针都指向数组的第一个元素。

接下来，我们遍历数组 \(nums\) 中的每个元素 \(x\)，对于每个元素 \(x\)，我们将 \(x\) 的出现次数加一，然后判断当前子数组是否满足要求。如果当前子数组不满足要求，我们就将指针 \(l\) 右移一位，并将 \(nums[l]\) 的出现次数减一，直到当前子数组满足要求为止。然后我们更新答案 \(ans = \max(ans, r - l + 1)\)。继续遍历，直到 \(r\) 到达数组的末尾。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(nums\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = l = 0
        cnt = defaultdict(int)
        for r, x in enumerate(nums):
            cnt[x] += 1
            while cnt[x] > k:
                cnt[nums[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int l = 0, r = 0; r < nums.length; ++r) {
            cnt.merge(nums[r], 1, Integer::sum);
            while (cnt.get(nums[r]) > k) {
                cnt.merge(nums[l++], -1, Integer::sum);
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int ans = 0;
        unordered_map<int, int> cnt;
        for (int l = 0, r = 0; r < nums.size(); ++r) {
            ++cnt[nums[r]];
            while (cnt[nums[r]] > k) {
                --cnt[nums[l++]];
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func maxSubarrayLength(nums []int, k int) (ans int) {
    cnt := make(map[int]int)
    for l, r := 0, 0; r < len(nums); r++ {
        cnt[nums[r]]++
        for cnt[nums[r]] > k {
            cnt[nums[l]]--
            l++
        }
        ans = max(ans, r-l+1)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function maxSubarrayLength(nums: number[], k: number): number {
    let ans = 0;
    const cnt = new Map<number, number>();
    for (let l = 0, r = 0; r < nums.length; ++r) {
        cnt.set(nums[r], (cnt.get(nums[r]) ?? 0) + 1);
        while (cnt.get(nums[r])! > k) {
            cnt.set(nums[l], cnt.get(nums[l])! - 1);
            ++l;
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn max_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
        let mut ans = 0;
        let mut cnt = std::collections::HashMap::new();

        let mut l = 0;
        for r in 0..nums.len() {
            *cnt.entry(nums[r]).or_insert(0) += 1;

            while cnt[&nums[r]] > k {
                *cnt.get_mut(&nums[l]).unwrap() -= 1;
                l += 1;
            }

            ans = ans.max((r - l + 1) as i32);
        }

        ans
    }
}

评论