給定整數陣列
nums和整數k，可以對任一元素加 1（最多操作 k 次），回傳操作後陣列中最高頻率的元素的頻率。
Example:
Input: nums = [1,2,4], k = 5 Output: 3（把 1 加到 4 需 3 次，把 2 加到 4 需 2 次，共 5 次，全部變成 4）
Intuition
TIP
核心思路：排序後用滑動視窗，嘗試把視窗內所有元素都提升到視窗最右邊的值，所需操作次數 = nums[right] * windowSize - windowSum，若 <= k 則合法。
- 只能增加不能減少，所以目標值一定是視窗內的最大值（即
nums[right]） - 排序後，讓相近的值在一起，這樣提升成本最低
- 所需操作 = 把所有元素都變成
nums[right]的差值總和
Approaches
1. Sort + Binary Search — O(n log n) / O(n)
- Idea: 排序後，對每個 right，用二分搜尋找到最左的 left，使得操作次數 <= k
- Time:
O(n log n)- 排序 + 二分 - Space:
O(n)- prefix sum
class Solution {
fun maxFrequency(nums: IntArray, k: Int): Int {
nums.sort()
val prefix = LongArray(nums.size + 1)
for (i in nums.indices) prefix[i + 1] = prefix[i] + nums[i]
var result = 1
for (right in nums.indices) {
var lo = 0
var hi = right
while (lo < hi) {
val mid = (lo + hi) / 2
val windowSize = right - mid + 1
val cost = nums[right].toLong() * windowSize - (prefix[right + 1] - prefix[mid])
if (cost <= k) hi = mid else lo = mid + 1
}
result = maxOf(result, right - lo + 1)
}
return result
}
}⭐ 2. Sort + Sliding Window — O(n log n) / O(1)
- Idea: 排序後，用可變大小滑動視窗，維護視窗總和；當操作成本超過 k 時收縮左邊界
- Time:
O(n log n)- 排序主導，滑動視窗 O(n) - Space:
O(1)- 原地排序
class Solution {
fun maxFrequency(nums: IntArray, k: Int): Int {
nums.sort()
var left = 0
var windowSum = 0L
var result = 1
for (right in nums.indices) {
windowSum += nums[right]
// 當前視窗要全部變成 nums[right] 的成本
while (nums[right].toLong() * (right - left + 1) - windowSum > k) {
windowSum -= nums[left]
left++
}
result = maxOf(result, right - left + 1)
}
return result
}
}WARNING
計算成本時要用 Long，因為 nums[right] * windowSize 可能溢位 Int。
🔑 Takeaways
- Pattern: 排序 + 可變大小滑動視窗
- Key trick: 「把視窗內元素全部提升到最大值」的成本公式 =
max * windowSize - windowSum，超過 k 就收縮左邊界