Leetcode 1838：最高频元素问题Java解法测试用例未通过排查

元素的**frequency（频率）**是其在数组中出现的次数。给定整数数组nums和整数k，每次操作可将数组中任意元素加1，求最多执行k次操作后，数组中元素的最大可能频率。

示例 #

• 输入：nums = [1,2,4], k = 5 → 输出：3（将前两个元素增至4，频率为3）
• 输入：nums = [1,4,8,13], k = 5 → 输出：2
• 输入：nums = [3,9,6], k = 2 → 输出：1

我写了暴力解法的Java代码，但在下面这个测试用例里没通过：

int[] nums = {9930,9923,9983,9997,9934,9952,9945,9914,9985,9982,9970,9932,9985,9902,9975,9990,9922,9990,9994,9937,9996,9964,9943,9963,9911,9925,9935,9945,9933,9916,9930,9938,10000,9916,9911,9959,9957,9907,9913,9916,9993,9930,9975,9924,9988,9923,9910,9925,9977,9981,9927,9930,9927,9925,9923,9904,9928,9928,9986,9903,9985,9954,9938,9911,9952,9974,9926,9920,9972,9983,9973,9917,9995,9973,9977,9947,9936,9975,9954,9932,9964,9972,9935,9946,9966};
int k = 3056 ;

我的代码输出是72，但预期结果是73。我手动统计也只得到72，想请人帮忙分析原因并给出解决方案。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        int maxFreq = 0;
        for (int i = 0; i < nums.length; i++) {
            int k_remaining = k;
            int curr_freq = 1;
            for (int j = 0; j < nums.length; j++) {
                if (i == j) continue; // 跳过自身
                if (nums[i] < nums[j]) continue; // 跳过比当前基准数大的元素
                if (k_remaining < 1) break;
                int diff = nums[i] - nums[j];
                if (diff <= k_remaining) {
                    ++curr_freq;
                    k_remaining = k_remaining - diff;
                }
            }
            if (curr_freq > maxFreq) maxFreq = curr_freq;
        }
        return maxFreq;
    }
}

问题分析 #

你的暴力解法存在两个核心问题：

1. 遍历顺序不合理：你遍历j时是从数组开头到结尾，没有优先选择和nums[i]差值最小的元素。这会导致你先把k消耗在提升差值大的元素上，后面差值小的元素反而没有足够的k去提升，最终统计的频率比实际能达到的数值小。比如测试用例中，部分差值极小的元素排在数组后半段，k提前耗尽后就无法被计入，而如果优先处理这些元素，就能凑出更多的有效数量。
2. 效率低下且易出错：O(n²)的时间复杂度面对大数组时不仅运行缓慢，还容易因为遍历顺序的问题出现计算偏差。

正确解法：滑动窗口法 #

最优思路是先对数组排序，再用滑动窗口寻找最大频率的窗口。排序后，窗口内的元素都小于等于右端元素，此时计算把窗口内所有元素提升到右端元素的总操作数，若不超过k就扩展窗口，否则缩小左边界。

代码实现 #

import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0;
        long total = 0;
        int maxFreq = 0;
        for (int right = 0; right < nums.length; right++) {
            // 计算当前窗口新增元素后，总操作数的增量
            if (right > 0) {
                total += (long)(nums[right] - nums[right-1]) * (right - left);
            }
            // 总操作数超过k时，移动左指针缩小窗口
            while (total > k) {
                total -= nums[right] - nums[left];
                left++;
            }
            // 更新最大频率
            maxFreq = Math.max(maxFreq, right - left + 1);
        }
        return maxFreq;
    }
}

原理说明 #

1. 排序：排序后，我们只需要考虑把窗口内的元素提升到窗口最右端的元素，这样所需操作数最少，能最大化利用k的操作次数。
2. 滑动窗口：
   • total记录当前窗口内所有元素提升到右端元素的总操作数，每次右移右指针时，计算新增的操作数。
   • 当total超过k，就移动左指针，减少窗口内的元素，直到总操作数符合要求。
   • 窗口的大小就是当前的频率，每次迭代更新最大频率。

测试用例验证 #

对于你提供的测试用例，排序后使用滑动窗口法能正确算出最大频率为73。因为排序后我们优先选择差值最小的元素组成窗口，把k用在了最能提升频率的地方，从而容纳更多元素。

内容的提问来源于stack exchange，提问作者Senthil