LeetCode 1838变体实现：允许元素递减时的最大频率求解

原问题回顾 #

LeetCode 1838 要求仅能对数组元素执行递增操作，求最多k次操作后元素的最大频率，基础滑动窗口解法如下：

def maxFrequency(self, nums: List[int], k: int) -> int:
    nums.sort()
    left = 0
    max_freq, currwindowsum = 0, 0

    for right in range(len(nums)):
        currwindowsum += nums[right]

        while nums[right]*(right-left+1) > currwindowsum + k:
            currwindowsum -= nums[left]
            left += 1

        max_freq = max(max_freq, right-left+1)

    return max_freq

该逻辑是将窗口内所有元素递增到窗口右边界元素，通过判断所需操作数是否超过k来调整窗口范围。

允许双向调整（含递减）的解法 #

当允许对元素执行递增或递减操作时，我们可以将窗口内元素调整到某个中间值（最优为中位数），以最小化操作数，进而找到最长的可行窗口。

核心思路 #

1. 先对数组升序排序，便于计算调整到任意元素的操作数。
2. 计算前缀和数组，快速获取窗口内元素总和，降低操作数计算复杂度。
3. 滑动窗口遍历数组，对每个右边界，调整左边界以确保当前窗口内存在某个元素，使得调整到该元素的总操作数不超过k。
4. 记录过程中最大的窗口长度，即为最大频率。

代码实现 #

def maxFrequency(self, nums: List[int], k: int) -> int:
    nums.sort()
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    
    left = 0
    max_freq = 0
    for right in range(n):
        # 调整左边界，确保当前窗口可行
        while True:
            length = right - left + 1
            mid = left + length // 2
            # 计算将窗口内所有元素调整到中位数nums[mid]的总操作数
            left_cost = nums[mid] * (mid - left) - (prefix[mid] - prefix[left])
            right_cost = (prefix[right+1] - prefix[mid+1]) - nums[mid] * (right - mid)
            total_cost = left_cost + right_cost
            if total_cost > k:
                left += 1
            else:
                break
        max_freq = max(max_freq, right - left + 1)
    return max_freq

逻辑说明 #

• 前缀和数组：prefix[i]表示前i个元素的总和，用于快速计算任意窗口内的元素和。
• 操作数计算：对于窗口[left, right]，选择中位数nums[mid]作为目标值，left_cost是窗口左半部分元素递增到nums[mid]的操作数，right_cost是窗口右半部分元素递减到nums[mid]的操作数，两者之和即为总操作数。
• 窗口调整：如果当前窗口的最小操作数（调整到中位数）超过k，则左边界右移，缩小窗口范围，直到操作数符合要求。

示例验证 #

对于输入nums=[1,2,4]、k=3：

1. 排序后数组为[1,2,4]，前缀和为[0,1,3,7]。
2. 当右边界到2（元素4）时，窗口为[0,2]，中位数是索引1的元素2。
3. 计算总操作数：(2-1)+(2-2)+(4-2)=3，刚好等于k，窗口长度3，因此最大频率为3。

内容的提问来源于stack exchange，提问作者U_H