我们遍历数组,收集每种不同元素出现的位置。
假设对于元素A,它出现的所有的index都放入pos数组里。那么对于以pos[i]为左边界的subarray,我们向右寻找一个最远的pos[j],使得两个位置之间的“非A元素”的数量恰好小于等于k,那么就意味着这个区间可以通过有限的删除操作变成equal A的subarray。数学表达式为:
if (pos[j]-pos[i]+1 - (j-i+1) <= k)
ret = max(ret, j-i+1)
显然,随着i的移动,j必然也是单向移动的。所以在pos数组上的快慢指针的移动,可以找出所有符合要求的区间,找到其中A元素最多的一段。
同理,处理其他的元素对应的pos数组,返回全局最大的解。