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