给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
1. 哈希分组 + 反悔队列
蠢逼做法
class Solution {
public:
int longestEqualSubarray(vector<int>& nums, int k) {
int res = 0;
unordered_map<int,vector<int>> m;
for(int i=0;i<nums.size();i++)
m[nums[i]].push_back(i);
for(auto &[_,arr]:m){
int n = arr.size(); //尝试进行连接
int cur = 0; //当前等值子数组长度
queue<pair<int,int>> q;//反悔队列
int tricks = k;
int pre = arr[0]-1;
int loss = 0;//被舍弃掉的
for(auto idx:arr){
int interval = idx - pre - 1;
if(interval==0) cur++;////连续的相同元素
else if(interval<=tricks){//通过删除进行连接
tricks-=interval;
q.push({interval,cur});//存储反悔可以获得的tricks，和失去的数
cur++;
}
else if(interval<=k){//可以通过反悔连接
while(interval>tricks){
tricks+=q.front().first;
loss = q.front().second; //更新丢失的数
q.pop();//删除
}
tricks-=interval;
q.push({interval,cur});//存储反悔可以获得的tricks，和失去的数
cur++;
}
else{//重新开辟
cur = 1;
loss = 0;
q = queue<pair<int,int>>();
tricks = k;
}
pre = idx;
res = max(res,cur-loss);
}
}
return res;
}
};
2. 哈希分组 + 预处理 + 双指针
用双指针代替反悔队列,使用vector会比哈希更快，同时将相邻的归为一组
class Solution {
public:
int longestEqualSubarray(vector<int> &nums, int k) {
int n = nums.size(), ans = 0;
vector<vector<int>> pos(n + 1);
for (int i = 0; i < n; i++)
pos[nums[i]].push_back(i - pos[nums[i]].size());
for (auto &ps: pos) {
int left = 0;
for (int right = 0; right < ps.size(); right++) {
while (ps[right] - ps[left] > k) // 要删除的数太多了
left++;
ans = max(ans, right - left + 1);
}
}
return ans;
}
};