目标
给你一个下标从 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^5
- 1 <= nums[i] <= nums.length
- 0 <= k <= nums.length
思路
给定一个数组 nums 和一个正整数k，最多可以删除数组中k个元素，问数组中最长的等值子数组有多长，所谓等值子数组就是数组中的值完全相同。
直接的想法是记录每个相同元素的下标index，然后计算它们之间的距离 gap，使用滑动窗口来计算最多可以消除的 gap 数量。
注意不能优先消除序列中距离小的 gap，也就是说只能按照顺序去消除，否则可能会截断等值子数组。
刚开始使用哈希表记录相同元素的下标序列，结果提示超出内存限制，后来改用数组解决了问题。
Map在不断添加元素时可能需要进行扩容，每次扩容都需要重新分配更大的内存空间。但我直接指定初始大小还是超出限制。
原来用了两个哈希表，indexMap 与 gapMap，后来 indexMap 改成了 List[]，gapMap 则直接在循环中计算并添加到 ArrayList 中。
注意这不是一个固定大小的窗口，如果按照固定大小的窗口去实现还是会超时。
代码
/**
* @date 2024-05-23 0:11
*/
public class LongestEqualSubarray2831 {
public int longestEqualSubarray_v1(List<Integer> nums, int k) {
if (nums.size() == 0) {
return 0;
}
int res = 0;
List<Integer>[] indexMap = new List[100001];
for (int i = 0; i < nums.size(); i++) {
int val = nums.get(i);
if (indexMap[val] == null) {
indexMap[val] = new ArrayList<>();
}
indexMap[val].add(i);
}
for (List<Integer> index : indexMap) {
if (index == null) {
continue;
}
int i = 0;
ArrayList<Integer> gaps = new ArrayList<>();
for (int j = 1; j < index.size(); j++) {
gaps.add(index.get(j) - index.get(i++) - 1);
}
int cnt = k;
int gapNums = 0;
int left = 0;
int right = 0;
while (right < gaps.size()) {
while (cnt >= 0 && right < gaps.size()) {
cnt -= gaps.get(right);
if (cnt >= 0) {
right++;
}
}
gapNums = Math.max(gapNums, right - left);
while (left < gaps.size() && cnt < 0) {
cnt += gaps.get(left);
left++;
}
right++;
}
res = Math.max(res, gapNums + 1);
}
return res;
}
}性能
又是勉强通过。//todo 性能分析与优化
