每日leetcode第0055天 1838. Frequency of the Most Frequent Element

这是一道超级有趣的滑动窗口题目。

首先我们知道我们可以把大的数字定成目标,让小的数字往大的数字凑。

其次我们知道需要找比目标小的,但是离他最近的数字去凑比较有效率。

所以我们要先将数组进行排序。

排序完成后,我们可以使用低位优先和高位优先两种方案,我选择高位优先。

我先将目标定在了最大的数字上面。左指针一直往左滑,每滑一次计算差值,记录window内的k。和k进行比较,如果大于k了就说明装不下了,停止左指针滑动。

装不下后,我们就可以计算能装下的数字的数量和最终结果的频率比较,取大者。

然后修改减小右指针。在这里我们减小右指针的同时我们得思考,window内k的复用性来减少时间复杂度。其实window内k的数值大概率会减小,减小的数值是元素内排除右指针元素的个数再乘以右指针和未来的右指针的元素的差值。

譬如:12358,内k值为7+6+5+3,右指针减小后1235,内k值为4+3+2。

好,到这里其实还没有完结。我们要进行收尾工作。

当左指针滑到0的时候,我们的左指针就不应该继续滑动了。

这时虽然左指针到了0,但还存在两种情况,一种是刚好滑到了0,下标0的元素装得下,window内k值不会爆。那这个时候当前的元素个数就是right – left + 1。但如果window内k值爆了,下标0元素装不下,这个时候当前的元素个数就是right – left。

如果是爆了,还需要继续再滑右指针去试探更大结果吗?其实不需要了,因为左指针就算能包进去,也就加了1个元素,而右指针一减就会少1个元素。

所以左指针一旦滑到0后,就可以判断比较输出返回了。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。