题目描述
给你一个下标从 0 开始的整数数组 nums
和一个整数 k
。
如果子数组中所有元素都相等,则认为子数组是一个 等值子数组。注意,空数组是 等值子数组。
从 nums
中删除最多 k
个元素后,返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。
样例
输入:nums = [1,3,2,3,1,3], k = 3
输出:3
解释:最优的方案是删除下标 2 和下标 4 的元素。
删除后,nums 等于 [1, 3, 3, 3]。
最长等值子数组从 i = 1 开始到 j = 3 结束,长度等于 3。
可以证明无法创建更长的等值子数组。
输入: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
算法
(双指针) $O(n)$
- 我们可以枚举数字,判定这个数字可构成的最长等值子数组的长度。
- 预处理每个数字出现的所有下标。
- 枚举数字,通过双指针找到这个数字可以间隔的最长不超过 $k$ 个其他数字的长度。具体地,对于位置 $i$,都维护 $j$,如果 $i$ 和 $j$ 之间其他数字的个数超过了 $k$,则需要移动 $j$。这样的 $j$ 是单调不减的。
时间复杂度
- 预处理的时间复杂度为 $O(n)$。
- 枚举数字时,每个下标最多被遍历两次。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储所有数字的下标。
C++ 代码
class Solution {
public:
int longestEqualSubarray(vector<int>& nums, int k) {
const int n = nums.size();
vector<vector<int>> p(n);
for (int i = 0; i < n; i++)
p[nums[i] - 1].push_back(i);
int ans = 0;
for (int num = 0; num < n; num++) {
int tot = 0, ma = 1;
for (int i = 1, j = 0; i < p[num].size(); i++) {
tot += p[num][i] - p[num][i - 1] - 1;
while (tot > k) {
tot -= p[num][j + 1] - p[num][j] - 1;
++j;
}
ma = max(ma, i - j + 1);
}
ans = max(ans, ma);
}
return ans;
}
};