1838. Frequency of the Most Frequent Element - Medium

前往題目

想法

• Sliding window

思路

1. 排序，由小到大
2. 左右指針都從0開始
3. 每次紀錄當前總數
4. 當window不合法時要移動左指針
5. 如果當前window較大，選擇其為新的最大值
6. 每個循環都移動右指針

這題的關鍵是如何判斷window不合法

Code

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);

        int l = 0, r = 0;
        // 使用long否則會溢出
        long res = 0L, total = 0;
        
        // Until the end
        while (r < nums.length) {
            // Store the total
            total += nums[r];

            // When the window is invalid
            // 判斷當前所有數字是否能全部變成右指針指向的數字
            while (nums[r] * (r - l + 1L) > total + k) {
                // Move the pointer
                total -= nums[l];
                ++l;
            }

            // 更新最大值
            res = Math.max(res, r - l + 1L);
            ++r;
        }
        return (int)res;
    }
}