2024年5月23日每日一题--2831. 找出最长等值子数组

https://leetcode.cn/problems/find-the-longest-equal-subarray/description/

题目分析

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。

从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。

子数组 是数组中一个连续且可能为空的元素序列。

示例 1：

输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优的方案是删除下标 2 和下标 4 的元素。
删除后，nums 等于 [1, 3, 3, 3] 。
最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
可以证明无法创建更长的等值子数组。

示例 2：

输入：nums = [1,1,2,2,1,1], k = 2
输出：4
解释：最优的方案是删除下标 2 和下标 3 的元素。
删除后，nums 等于 [1, 1, 1, 1] 。
数组自身就是等值子数组，长度等于 4 。
可以证明无法创建更长的等值子数组。

提示：

• 1 <= nums.length <= 10<sup>5</sup>
• 1 <= nums[i] <= nums.length
• 0 <= k <= nums.length

方案一

import java.util.HashMap;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0,
                right = 1,
                error_num = 0,
                all_num = 1,
                max = nums.get(0);
        map.put(max, 1);
        for (; right < nums.size(); right++) {
            all_num++;
            if (max == nums.get(right)) {
                map.put(max, map.get(max) + 1);
            } else {
                error_num++;
                ans = Math.max(ans, all_num - error_num);
                map.put(nums.get(right), map.getOrDefault(nums.get(right), 0) + 1);
                max = findMax(map, nums.get(left), map.get(nums.get(left)));
                error_num = all_num - map.get(max);
                if (error_num > k) {
                    while (left < right && error_num > k) {
                        all_num--;
                        if (nums.get(left) == max) {
                            map.put(max, map.get(max) - 1);
                        } else {
                            map.put(nums.get(left), map.get(nums.get(left)) - 1);
                            error_num--;
                            left++;
                            break;
                        }
                        left++;
                        max = findMax(map, nums.get(left), map.get(nums.get(left)));
                        error_num = all_num - map.get(max);
                    }

//                    System.out.println(max);
                }
            }
        }
        ans = Math.max(ans, all_num - error_num);
        ans = Math.max(ans, map.get(findMax(map, 0, 0)));
//        System.out.println(all_num);
//        System.out.println(error_num);
        return ans;
    }

    public int findMax(HashMap<Integer, Integer> map, Integer maxKey, Integer maxValue) {
//        int maxKey = 0,
//                maxValue = 0;
        for (Integer key : map.keySet()) {
//            System.out.println(key + " = " + map.get(key));
            if (map.get(key) > maxValue) {
                maxValue = map.get(key);
                maxKey = key;
            }
        }
//        System.out.println();
        return maxKey;
    }
}

结果

分析

时间复杂度：
O( n * k )

空间复杂度：
O( k )

官方题解

https://leetcode.cn/problems/find-the-longest-equal-subarray/solutions/2784932/zhao-chu-zui-chang-deng-zhi-zi-shu-zu-by-vcnw/

方法一：滑动窗口

思路与算法

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) {
            pos.computeIfAbsent(nums.get(i), x -> new ArrayList<>()).add(i);
        }
        int ans = 0;
        for (List<Integer> vec : pos.values()) {
            for (int i = 0, j = 0; i < vec.size(); i++) {
                /* 缩小窗口，直到不同元素数量小于等于 k */
                while (vec.get(i) - vec.get(j) - (i - j) > k) {
                    j++;
                }
                ans = Math.max(ans, i - j + 1);
            }
        }
        return ans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-longest-equal-subarray/solutions/2784932/zhao-chu-zui-chang-deng-zhi-zi-shu-zu-by-vcnw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：一次遍历优化

思路与算法

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0, j = 0; j < n; j++) {
            cnt.put(nums.get(j), cnt.getOrDefault(nums.get(j), 0) + 1);
            /*当前区间中，无法以 nums[i] 为等值元素构成合法等值数组*/
            while (j - i + 1 - cnt.get(nums.get(i)) > k) {
                cnt.put(nums.get(i), cnt.get(nums.get(i)) - 1);
                i++;
            }
            ans = Math.max(ans, cnt.get(nums.get(j)));
        }
        return ans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-longest-equal-subarray/solutions/2784932/zhao-chu-zui-chang-deng-zhi-zi-shu-zu-by-vcnw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。