3422：将子数组元素变为相等所需的最小操作数（★）

Ian

2025-01-14 约 480 字预计阅读 1 分钟次阅读

力扣第 3422 题

题目

给定一个整数数组 nums 和一个整数 k。你可以进行任意次以下操作：

给 nums 的任何元素增加或减少 1。

返回确保至少有一个大小为 k 的 nums 中的子数组的所有元素都相等的所需的最小操作数。

示例 1：

输入：nums = [4,-3,2,1,-4,6], k = 3

输出：5

解释：

使用 4 次操作来给 nums[1] 增加 4。结果数组为 [4, 1, 2, 1, -4, 6]。
使用 1 次操作来给 nums[2] 减少 1。结果数组为 [4, 1, 1, 1, -4, 6]。
现在数组包含一个大小为 k = 3 的子数组 [1, 1, 1]，所有元素都想等。因此，答案为 5。

示例 2：

输入：nums = [-2,-2,3,1,4], k = 2

输出：0

解释：

大小为 k = 2 的子数组 [-2, -2] 已经包含了所有相等的元素，所以不需要操作。因此答案为 0。

提示：

2 <= nums.length <= 10⁵
-10⁶ <= nums[i] <= 10⁶
2 <= k <= nums.length

相似问题：

分析

要维护滑动窗口中所有数到中位数的距离之和 s
可以用有序集合，添加删除时根据和中位数的关系维护 s 即可

解答

 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


class SL:
    def __init__(self,):
        self.sl = SortedList()
        self.s = 0

    def cal(self,x):
        if not self.sl:
            return 0
        n = len(self.sl)
        l,r = self.sl[(n-1)//2],self.sl[n//2]
        return l-x if x<l else x-r if x>r else 0

    def add(self,x):
        self.s += self.cal(x)
        self.sl.add(x)
    
    def remove(self,x):
        self.sl.remove(x)
        self.s -= self.cal(x)

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        sl = SL()
        res = inf
        for i,x in enumerate(nums):
            sl.add(x)
            if i>=k:
                sl.remove(nums[i-k])
            if i>=k-1:
                res = min(res,sl.s)
        return res

4062 ms

目录

3422：将子数组元素变为相等所需的最小操作数（★）

题目

分析

解答