[LeetCode] 2831. Find the Longest Equal Subarray

You are given a 0-indexed integer array nums and an integer k.

A subarray is called equal if all of its elements are equal. Note that the empty subarray is an equal subarray.

Return the length of the longest possible equal subarray after deleting at most k elements from nums.

A subarray is a contiguous, possibly empty sequence of elements within an array.

Example 1:
Input: nums = [1,3,2,3,1,3], k = 3
Output: 3
Explanation: It’s optimal to delete the elements at index 2 and index 4.
After deleting them, nums becomes equal to [1, 3, 3, 3].
The longest equal subarray starts at i = 1 and ends at j = 3 with length equal to 3.
It can be proven that no longer equal subarrays can be created.

Example 2:
Input: nums = [1,1,2,2,1,1], k = 2
Output: 4
Explanation: It’s optimal to delete the elements at index 2 and index 3.
After deleting them, nums becomes equal to [1, 1, 1, 1].
The array itself is an equal subarray, so the answer is 4.
It can be proven that no longer equal subarrays can be created.

Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= nums.length
0 <= k <= nums.length

找出最长等值子数组。

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

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

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

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

思路

思路是滑动窗口。题目的最终目标是让我们找到一个最长的等值子数组。准确地说与其说是子数组，不如说是子序列，因为最终题目要求的最长的子数组里面的元素的下标并不是连续的。

这里我们需要一个 hashmap，key 是每个不同元素，value 是一个 queue，存储的是当前元素在 input 数组内出现的下标。然后我们开始遍历 input 数组，根据遇到的不同元素，把他们的下标都放到各自对应的 queue 中。每当放入一个下标的时候，我们判断，如果当前这个元素能组成最长的等值子数组，那么他第一次出现的下标（假设为 i）和最后一次出现的下标（假设为 j）之间的距离一定要满足 i + k <= j。如果不满足这个条件，说明 i 和 j 距离太远，需要从 i 开始删除一些元素，直到满足题目条件为止。

通常情况，i 和 j 之间的距离一定比这个元素实际的个数要大，因为中间夹杂了其他的元素，但是我们要保证其中夹杂的其他元素的个数 <= k。而当前这个相同元素的实际个数 = queue.size()。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        HashMap<Integer, Deque<Integer>> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums.get(i);
            if (!map.containsKey(num)) {
                map.put(num, new ArrayDeque<>());
            }
            map.get(num).offerLast(i);
            Deque<Integer> q = map.get(num);
            while (!q.isEmpty() && i - q.peekFirst() + 1 > q.size() + k) {
                q.pollFirst();
            }
            res = Math.max(res, q.size());
        }
        return res;
    }
}