题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，可以对其中任意数字做加一操作，最多 k 次，求操作后，数组内最高频的数字的数目是多少。

思路分享

  • 总得来说就是不定长滑动窗口，但是具体实现比较多样，陆爻齐下面提供两种思路。一种是自己想出来的，另一种看别人题解，自己实现总结的。

  • 第一种，陆爻齐审完题发现，本题要想通过滑动窗口解决，先需排序，就像【Leetcode Daily】2779数组的最大美丽值一样。排序后，通过窗口右侧，窗口长度就能计算窗口与右侧同步后的总和，以及滑动窗口可以方便计算当前和，这样就能计算出差值。而窗口的不满足条件则设定为该差值大于 k，就让左窗口滑动，更新窗口目标和与当前和，直到符合。

  • 另一种，算是上面思路的一些简化。对于排序后的窗口，其实用下面的方法就能方便地计算窗口目标和与当前和的差值。上面的思路聚焦于“和”，而本思路直接计算“差值”。每次窗口向右滑，则把新值与其左侧邻居之差乘以新窗口长度减一加到差值上。这么做可以在每次更新右侧的值时，快速地把其与剩余元素的差值计算出来，由于上一次也这么同步了，所以就计算新值与其左侧邻居之差；而新窗口右侧的值与自己差值为 0，所以只用乘以新窗口长度减一。这样一来，窗口不满足条件就好写了，就是该差值大于 k。

代码解答（强烈建议自行解答后再看）

  • 陆爻齐想的参考解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        long long cur_sum = 0;
        int ans = 0;
        int left = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            cur_sum += nums[i];
            long long tar_sum = (long long)nums[i]*(i-left+1);
            while(tar_sum-cur_sum>k) {
                //cout << "i:" << i << ";left:" << left << ";tar_sum:" << tar_sum << ";cur_sum:" << cur_sum << endl;
                tar_sum -= nums[i];
                cur_sum -= nums[left++];
            }
            ans = max(ans, i-left+1);
        }
        return ans;
    }
};
  • 陆爻齐参考其它题解的参考解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        if (nums.size()==1) return 1;
        long long cur_dif = 0;
        int ans = 0;
        int left = 0;
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++) {
            cur_dif += (long long)(nums[i]-nums[i-1])*(i-left); // 不加一是因为最右边不用加数值
            while(cur_dif>k) {
                cur_dif -= (nums[i]-nums[left++]);
            }
            //cout << "i:" << i << ";left:" << left << ";cur_dif:" << cur_dif << endl;
            ans = max(ans, i-left+1);
        }
        return ans;
    }
};