Leetcode 3434. Maximum Frequency After Subarray Operation

• Leetcode 3434. Maximum Frequency After Subarray Operation
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3434. Maximum Frequency After Subarray Operation

1. 解题思路

这一题的话我们只需要考察所有的数$i$转换为$k$时所能够形成的最大的值。

而对于这个问题，事实上就是我们要考察任意序列当中$i$和$k$的差值的最大值，这个我们可以通过一个累积数组进行实现，我们不断记录当前$i$和$k$的累计次数差值，以及此前出现过的最小的差值，两者相减就是将$i$转换为$k$所能够获得的最大的值。

2. 代码实现

给出python代码实现如下：

class Solution:def maxFrequency(self, nums: List[int], k: int) -> int:cnt = Counter(nums)[k]ans = cntfor t in range(1, 51):if t == k:continuepre_min, delta, max_delta = 0, 0, 0for x in nums:if x == k:delta -= 1elif x == t:delta += 1max_delta = max(delta - pre_min, max_delta)pre_min = min(delta, pre_min)ans = max(ans, cnt+max_delta)return ans

提交代码评测得到：耗时5715ms，占用内存21.7MB。