給你一個下標從 0 開始的整數數組 nums 和一個整數 k 。

你可以對數組執行 至多 k 次操作：

從數組中選擇一個下標 i ，將 nums[i] 增加 或者 減少 1 。
最終數組的頻率分數定義為數組中眾數的 頻率 。

請你返回你可以得到的 最大 頻率分數。

眾數指的是數組中出現次數最多的數。一個元素的頻率指的是數組中這個元素的出現次數。

示例 1：

輸入：nums = [1,2,6,4], k = 3
輸出：3
解釋：我們可以對數組執行以下操作：

• 選擇 i = 0 ，將 nums[0] 增加 1 。得到數組 [2,2,6,4] 。
• 選擇 i = 3 ，將 nums[3] 減少 1 ，得到數組 [2,2,6,3] 。
• 選擇 i = 3 ，將 nums[3] 減少 1 ，得到數組 [2,2,6,2] 。
  元素 2 是最終數組中的眾數，出現了 3 次，所以頻率分數為 3 。
  3 是所有可行方案里的最大頻率分數。
  示例 2：

輸入：nums = [1,4,4,2,4], k = 0
輸出：3
解釋：我們無法執行任何操作，所以得到的頻率分數是原數組中眾數的頻率 3 。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= k <= 10^14

法一：對于一個子數組，要使操作次數最小，最優解是所有數字都變成中位數，因此我們可以先對數組進行排序，然后用滑窗來解，對于一個子數組的操作次數，可以用前綴和來解決，如下圖：

將子數組里所有數字都變為q，所需的操作次數就是藍色和綠色部分的面積，藍色部分的面積可以用矩形面積減去前三個數字的前綴和得到，綠色部分的面積可以用后三個數字的前綴和減去下面的矩形得到。

class Solution {
public:int maxFrequencyScore(vector<int>& nums, long long k) {sort(nums.begin(), nums.end());vector<long long> s(nums.size() + 1);for (int i = 0; i < nums.size(); ++i) {s[i + 1] = s[i] + nums[i];}auto getDistance = [&](int l, int i, int r) -> long long {long long left = (long long)nums[i] * (i - l) - (s[i] - s[l]);long long right = s[r + 1] - s[i + 1] - (long long)nums[i] * (r - i);return left + right;};int left = 0;int ans = 0;for (int i = 0; i < nums.size(); ++i) {while (getDistance(left, (i + left) / 2, i) > k) {++left;}ans = max(ans, i - left + 1);}return ans;}
};

如果nums的長度為n，則此算法時間復雜度為O(nlogn)，空間復雜度為O(n)。

法二：先對nums進行排序，然后滑窗，考慮一個子數組，如果子數組現在有3個元素a0、a1、a2，此時最優解是將a0和a2變為a1，操作次數s3為(a2 - a1) + (a1 - a0) = a2 - a0，此時滑窗的右端點向右移動了，那么此時子數組包含4個元素a0、a1、a2、a3，此時最優解是將所有元素變為a1，操作次數s4為(a1 - a0) + (a2 - a1) + (a3 - a1) = a2 + a3 - a0 - a1，同理，如果有五個元素，則操作次數s5為(a2 - a0) + (a2 - a1) + (a3 - a2) + (a4 - a2) = a3 + a4 - a0 - a1，可見，每個子數組的最優操作次數都是中位數右邊的所有數減去中位數左邊的所有數。因此，當新加進來一個數時，它對操作次數的貢獻總是它自己的值，并且當一個數加入時，中位數會變為負數，可以用s5減去s4的值，即a4 - a2來表示，這是加入新值后總元素數為奇數的情況，為偶數時同理，用s4減去s3可得a3 - a1，即新加入一個下標為i的數字對操作次數的貢獻為nums[i] - nums[(i + left)/2。當左邊的數字出滑窗時，左邊的數字對總操作次數的貢獻為nums[left]，因為它原本對操作次數的貢獻為負，出滑窗時要加上它，并且中位數由正變為負，即總貢獻為nums[left] - nums[(i + left) / 2]：

class Solution {
public:int maxFrequencyScore(vector<int>& nums, long long k) {sort(nums.begin(), nums.end());int left = 0;int ans = 0;long long cur = 0;for (int i = 0; i < nums.size(); ++i) {cur += nums[i] - nums[(i + left) / 2];while (cur > k) {cur += nums[left] - nums[(i + left + 1) / 2];++left;}ans = max(ans, i - left + 1);}return ans;}
};

如果nums的長度為n，則此算法時間復雜度為O(nlogn)，空間復雜度為O(1)。