Leetcode 3434. Maximum Frequency After Subarray Operation
- Leetcode 3434. Maximum Frequency After Subarray Operation
- 1. 解题思路
- 2. 代码实现
- 题目链接：3434. Maximum Frequency After Subarray Operation
1. 解题思路
这一题的话我们只需要考察所有的数 i i i转换为 k k k时所能够形成的最大的值。
而对于这个问题，事实上就是我们要考察任意序列当中 i i i和 k k k的差值的最大值，这个我们可以通过一个累积数组进行实现，我们不断记录当前 i i i和 k k k的累计次数差值，以及此前出现过的最小的差值，两者相减就是将 i i i转换为 k k k所能够获得的最大的值。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
cnt = Counter(nums)[k]
ans = cnt
for t in range(1, 51):
if t == k:
continue
pre_min, delta, max_delta = 0, 0, 0
for x in nums:
if x == k:
delta -= 1
elif x == t:
delta += 1
max_delta = max(delta - pre_min, max_delta)
pre_min = min(delta, pre_min)
ans = max(ans, cnt+max_delta)
return ans
提交代码评测得到：耗时5715ms，占用内存21.7MB。