1838. 最高频元素的频数

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        # 以下是读题读错了，k看成了 每次都可以最多执行k次，题意中k像个水缸，总量有限。
        # def search_II(check)->int:
        #     left = 1
        #     right = len(nums)
        #     while left<=right:
        #         mid = (left+right)>>1
        #         if check(mid):
        #             left = mid+1
        #         else:
        #             right = mid-1
        #     return right
        # def check(x):  # 频数是x
        #     nums.sort()
        #     max_frequency = 0
        #     for i in range(len(nums)):
        #         #注意 bisect 查找是贪婪的
        #         idx = bisect.bisect_right(nums,k+nums[i])
        #         max_frequency = max(max_frequency, idx - i)
        #     print(x,max_frequency,max_frequency >= x)
        #     return max_frequency >= x
        # return search_II(check)
        
        # k 总量一定，我们用 滑动窗口来解决更简单。
        # 滑动窗口模板
        # left,right = 0, (0 or 1)
        # ret = total = 0
        # while right < len(nums):
        #    更新total值
        #    while 窗口内数据不满足要求
        #       1. 更新total值
        #       2. 收缩左边界
        #    更新ret最大值
        # 返回 ret
        nums.sort()
        n = len(nums)
        left = 0
        diff = 0
        ans = 1
        for right in range(1,n):
            diff += (nums[right]-nums[right-1])*(right-left)
            while diff>k:
                diff -= nums[right] - nums[left] 
                left += 1
            ans = max(ans,right-left+1)
        return ans