1838.最高頻元素的頻數(shù)
難度：中等
題目
元素的 頻數(shù) 是該元素在一個(gè)數(shù)組中出現(xiàn)的次數(shù)莺治。
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 。在一步操作中，你可以選擇 nums 的一個(gè)下標(biāo)，并將該下標(biāo)對(duì)應(yīng)元素的值增加 1 遭铺。
執(zhí)行最多 k 次操作后，返回?cái)?shù)組中最高頻元素的 最大可能頻數(shù) 。
提示：
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
- 1 <= k <= 10^5
示例
示例 1：
輸入：nums = [1,2,4], k = 5
輸出：3
解釋：對(duì)第一個(gè)元素執(zhí)行 3 次遞增操作掂僵，對(duì)第二個(gè)元素執(zhí) 2 次遞增操作航厚，此時(shí) nums = [4,4,4] 。
4 是數(shù)組中最高頻元素锰蓬，頻數(shù)是 3 。
示例 2：
輸入：nums = [1,4,8,13], k = 5
輸出：2
解釋：存在多種最優(yōu)解決方案：
- 對(duì)第一個(gè)元素執(zhí)行 3 次遞增操作眯漩，此時(shí) nums = [4,4,8,13] 芹扭。4 是數(shù)組中最高頻元素，頻數(shù)是 2 赦抖。
- 對(duì)第二個(gè)元素執(zhí)行 4 次遞增操作舱卡，此時(shí) nums = [1,8,8,13] 。8 是數(shù)組中最高頻元素队萤，頻數(shù)是 2 轮锥。
- 對(duì)第三個(gè)元素執(zhí)行 5 次遞增操作，此時(shí) nums = [1,4,13,13] 要尔。13 是數(shù)組中最高頻元素舍杜，頻數(shù)是 2 。
示例 3：
輸入：nums = [3,9,6], k = 2
輸出：1
分析
腦回路是這樣的...
剛開始赵辕，這題有點(diǎn)難既绩，嗯用例范圍10^5，放棄多重循環(huán)的暴力吧.
看到示例3还惠，沒毛病不管會(huì)不會(huì)饲握，至少先排個(gè)序吧。
在瞅示例1吧蚕键，前綴和救欧，貌似也不對(duì)？拿[1, 2, 4]來說锣光，1-2是1笆怠，2-4是2，那1-4不是還要加一次2嫉晶。還要加一次骑疆？
那不就是每次右移一位，需要增加(right - left) * (nums[right] - nums[right -1])這么多數(shù)字替废。
那如果pre_sum不夠了箍铭，收縮下呢？就是nums[right] - nums[left]吧椎镣。好了诈火，想到這里解題基本就成型了。
我們使用一個(gè)滑動(dòng)窗口模板状答，默認(rèn)窗口拉伸冷守，當(dāng)pre_sum > k時(shí)刀崖，收縮左邊界。直至滿足條件拍摇，然后每次計(jì)算最大窗口距離：
# 滑動(dòng)窗口模板
left,right = 0, (0 or 1)
ret = total = 0
while right < len(nums):
更新total值
while 窗口內(nèi)數(shù)據(jù)不滿足要求
1. 更新total值
2. 收縮左邊界
更新ret最大值
返回 ret
解題
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
left, right, pre_sum, ret = 0, 1, 0, 1
while right < len(nums):
pre_sum += (right - left) * (nums[right] - nums[right - 1])
while pre_sum > k:
pre_sum -= nums[right] - nums[left]
left += 1
ret = max(ret, right - left + 1)
right += 1
return ret
歡迎關(guān)注我的公眾號(hào): 清風(fēng)Python亮钦，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)，了解更多python小知識(shí)充活。
我的個(gè)人博客：https://qingfengpython.cn
