Description
給定整數陣列
nums和整數k，可以對任一元素加 1（最多操作 k 次），回傳操作後陣列中最高頻率的元素的頻率。
Example:
Input: nums = [1,2,4], k = 5 Output: 3（把 1 加到 4 需 3 次，把 2 加到 4 需 2 次，共 5 次，全部變成 4）
Intuition#
核心思路：排序後用滑動視窗，嘗試把視窗內所有元素都提升到視窗最右邊的值，所需操作次數 =
nums[right] * windowSize - windowSum，若 <= k 則合法。
- 只能增加不能減少，所以目標值一定是視窗內的最大值（即
nums[right]） - 排序後，讓相近的值在一起，這樣提升成本最低
- 所需操作 = 把所有元素都變成
nums[right]的差值總和
Approaches#
1: 排序 + Binary Search#
- 概念: 排序後，對每個 right，用二分搜尋找到最左的 left，使得操作次數 <= k
- 時間複雜度:
O(n log n)- 排序 + 二分 - 空間複雜度:
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: 排序 + Sliding Window#
- 概念: 排序後，用可變大小滑動視窗，維護視窗總和；當操作成本超過 k 時收縮左邊界
- 時間複雜度:
O(n log n)- 排序主導，滑動視窗 O(n) - 空間複雜度:
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
}
}計算成本時要用
Long，因為nums[right] * windowSize可能溢位 Int。
🔑 Takeaways#
- Pattern: 排序 + 可變大小滑動視窗
- 關鍵技巧: 「把視窗內元素全部提升到最大值」的成本公式 =
max * windowSize - windowSum，超過 k 就收縮左邊界