最高频元素的频数 图解题解

这道题到底在问什么

输入

nums=[1,2,4], k=5

输出

3

先想最直接的笨办法

扫完全程,能在 10 次操作内抬成同一个值的最长窗口长 5,所以最高频数是 5。排序加滑窗,一遍就找到了,不用枚举抬哪个值。（动画第 25 步）

最优解：一步一步想明白

1. 3记住「排序 → 抬平代价 = 最大值×长度 − 窗口和 → 代价超 k 就左缩、记最长」,下面每一格都在套它。
2. 4第一步排序。排完序相邻的数才挨在一起,抬平代价最小,滑动窗口也才能稳稳伸缩。下面窗口从空开始,右指针一格格扩。
3. 5右指针到第 0 位(值 1)。把窗口里 1 个数都抬到最大的 1,要花 1×1 减去窗口和 1,也就是 0 次操作。没超过 k=10,这段抬得平。
4. 6窗口 [0, 0] 抬平只要 0 次(≤10),长度 1。比之前还长,最高频数刷新成 1。
5. 7右指针到第 1 位(值 2)。把窗口里 2 个数都抬到最大的 2,要花 2×2 减去窗口和 3,也就是 1 次操作。没超过 k=10,这段抬得平。
6. 8窗口 [0, 1] 抬平只要 1 次(≤10),长度 2。比之前还长,最高频数刷新成 2。
7. 9右指针到第 2 位(值 3)。把窗口里 3 个数都抬到最大的 3,要花 3×3 减去窗口和 6,也就是 3 次操作。没超过 k=10,这段抬得平。
8. 10窗口 [0, 2] 抬平只要 3 次(≤10),长度 3。比之前还长,最高频数刷新成 3。
9. 11右指针到第 3 位(值 4)。把窗口里 4 个数都抬到最大的 4,要花 4×4 减去窗口和 10,也就是 6 次操作。没超过 k=10,这段抬得平。
10. 12窗口 [0, 3] 抬平只要 6 次(≤10),长度 4。比之前还长,最高频数刷新成 4。
11. 13右指针到第 4 位(值 5)。把窗口里 5 个数都抬到最大的 5,要花 5×5 减去窗口和 15,也就是 10 次操作。没超过 k=10,这段抬得平。
12. 14窗口 [0, 4] 抬平只要 10 次(≤10),长度 5。比之前还长,最高频数刷新成 5。
13. 15右指针到第 5 位(值 6)。把窗口里 6 个数都抬到最大的 6,要花 6×6 减去窗口和 21,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。
14. 16左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [1, 5] 能全抬成 6、长度 5。没超过已记的最长 5,保持。
15. 17右指针到第 6 位(值 7)。把窗口里 6 个数都抬到最大的 7,要花 7×6 减去窗口和 27,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。
16. 18左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [2, 6] 能全抬成 7、长度 5。没超过已记的最长 5,保持。
17. 19右指针到第 7 位(值 8)。把窗口里 6 个数都抬到最大的 8,要花 8×6 减去窗口和 33,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。
18. 20左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [3, 7] 能全抬成 8、长度 5。没超过已记的最长 5,保持。
19. 21右指针到第 8 位(值 9)。把窗口里 6 个数都抬到最大的 9,要花 9×6 减去窗口和 39,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。
20. 22左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [4, 8] 能全抬成 9、长度 5。没超过已记的最长 5,保持。
21. 23右指针到第 9 位(值 12)。把窗口里 6 个数都抬到最大的 12,要花 12×6 减去窗口和 47,也就是 25 次操作。它 > k=10(红),操作不够,下一步得左缩。
22. 24左指针右移 3 步、把移出的数从和里减掉,代价降到 7(≤10)。现在窗口 [7, 9] 能全抬成 12、长度 3。没超过已记的最长 5,保持。
23. 25扫完全程,能在 10 次操作内抬成同一个值的最长窗口长 5,所以最高频数是 5。排序加滑窗,一遍就找到了,不用枚举抬哪个值。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        left = total = ans = 0
        for right, x in enumerate(nums):
            total += x
            while x * (right - left + 1) - total > k:
                total -= nums[left]
                left += 1
            ans = max(ans, right - left + 1)
        return ans

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long total = 0;
        int left = 0, ans = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            total += nums[right];
            while (1LL * nums[right] * (right - left + 1) - total > k) total -= nums[left++];
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        long total = 0;
        int left = 0, ans = 0;
        for (int right = 0; right < nums.length; right++) {
            total += nums[right];
            while ((long) nums[right] * (right - left + 1) - total > k) total -= nums[left++];
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

复杂度

面试官可能追问