Re: [閒聊] 每日LeetCode
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：
------------------------------------------------
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int res = 1;
int sum = 0;
int j = 0;
for (int i = 1; i < nums.length; i++) {
sum += (nums[i] - nums[i - 1]) * (i - j);
while (sum > k) {
sum -= nums[i] - nums[j];
j++;
}
res = Math.max(res, i - j + 1);
}
return res;
}
}
------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700316833.A.A1C.html
討論串 (同標題文章)
完整討論串 (本文為第 527 之 719 篇)：