1838. 最高频元素的频数 力扣（中等） 尺取法 是我做不出来的题

题目描述：

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

示例 1：

输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

题源：https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element/

题解：https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element/solution/1838-zui-gao-pin-yuan-su-de-pin-shu-shua-ub57/

代码：

啥也别说TLE来一发：

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
     sort(nums.begin(),nums.end());
     int res=1;
     for(int i=1;i<nums.size();i++)
     {
          int kk=k;
          int num=1;
          for(int j=i-1;j>=0;j--)
              if(kk>=nums[i]-nums[j])
              {
                  kk-=(nums[i]-nums[j]);
                  num++;
              } else break;
          res=max(res,num);
     }
     return res;
    }
};

 改进方法，尺取法

一次执行错误，应为int*int可能爆int

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
     sort(nums.begin(),nums.end());
     int res=1;
     int l=0;
     long long kk=0;
     for(int r=1;r<nums.size();r++)
     {
         kk+=(long long)(r-l)*(nums[r]-nums[r-1]);  // 必须使用long long否则数字会溢出
         while(kk>k)
             kk-=(nums[r]-nums[l++]);
        res=max(res,r-l+1);
     }
     return res;
    }
};