Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-11-18 22:13:50
https://leetcode.com/problems/frequency-of-the-most-frequent-element/description
1838. Frequency of the Most Frequent Element
给你一个阵列 nums 和一个数字 k,你可以对任意的 nums[i] 进行 k 次递增1操作,求出
0~k次操作后nums最多可能有几个相同的数字。
思路:
1.首先,如果一个数字 n 是出现最多的数字,那么 k 次递增操作一定是和 n 差距
最小的数字,所以我们先将原阵列做一次排序。
2.利用滑动窗口来不断往窗口内添加数字,窗口最右边的元素表示出现最多的数字,
如果窗口里面需要递增的数字大于k,则把窗口左边的数字pop直到满足成本 <= k。
3.若 j 为窗口左边指标,i 为窗口右边指标
窗口入队的成本:
新成本 = 旧成本 + nums[i](新的行) + (nums[i] - num[i-1]) * (i - j)
(填满旧的窗口顶部的成本)
窗口出队成本:
新成本 = 旧成本 - (nums[i] - nums[j]) (移除掉新窗口的第一行所需的成本)
4.遍历的过程用当前的窗口大小去更新答案即可。
Java Code:

Links booklink

Contact Us: admin [ a t ] ucptt.com