Kimi LeetCode 3505. 使 K 个子数组内元素相等的最少操作数 Python3实现

以下是 LeetCode 3505. 使 K 个子数组内元素相等的最少操作数的 Python3 实现---思路概述本题是 LeetCode 462最小操作次数使数组元素相等 II和 LeetCode 480滑动窗口中位数的结合题。核心思路1. 中位数贪心对于一个子数组要使其所有元素相等且操作次数最少最终值应取子数组的中位数。证明可参考 LeetCode 462。2. 滑动窗口中位数用对顶堆两个堆 延迟删除维护长度为 x 的滑动窗口快速求出每个窗口变为相等的最小操作次数 cost[i]。3. 划分型 DPdp[i][j] 表示前 i 个元素中选出 j 个不重叠的长度为 x 的子数组的最小操作数。- 不选dp[i][j] dp[i-1][j]- 选以 i-1 结尾的子数组dp[i][j] dp[i-x][j-1] cost[i-1]---完整 Python3 代码pythonfrom typing import Listimport heapqclass Solution:def minOperations(self, nums: List[int], x: int, k: int) - int:n len(nums)INF 10**18# Step 1: Preprocess cost[i]# cost[i] min operations to make subarray nums[i-x1..i] all equal# Use dual heap with lazy deletion to maintain sliding window mediancost [INF] * n# Two heaps: small (max-heap for smaller half), large (min-heap for larger half)small [] # max-heap, store negativeslarge [] # min-heapdelayed {} # lazy deletion dictsmall_size 0large_size 0small_sum 0large_sum 0small_target x // 2large_target x - small_targetdef prune(heap):while heap:num -heap[0] if heap is small else heap[0]if delayed.get(num, 0) 0:delayed[num] - 1if delayed[num] 0:del delayed[num]heapq.heappop(heap)else:breakdef make_balance():nonlocal small_size, large_size, small_sum, large_sumif small_size small_target:num -heapq.heappop(small)small_sum - numsmall_size - 1heapq.heappush(large, num)large_sum numlarge_size 1prune(small)elif large_size large_target:num heapq.heappop(large)large_sum - numlarge_size - 1heapq.heappush(small, -num)small_sum numsmall_size 1prune(large)def insert(num):nonlocal small_size, large_size, small_sum, large_sumif not small or num -small[0]:heapq.heappush(small, -num)small_sum numsmall_size 1else:heapq.heappush(large, num)large_sum numlarge_size 1make_balance()def erase(num):nonlocal small_size, large_size, small_sum, large_sumdelayed[num] delayed.get(num, 0) 1if small and num -small[0]:small_size - 1small_sum - numif num -small[0]:prune(small)else:large_size - 1large_sum - numif large and num large[0]:prune(large)make_balance()def get_median():return large[0]def get_cost():median get_median()cost_small median * small_size - small_sumcost_large large_sum - median * large_sizereturn cost_small cost_large# Initialize first windowfor i in range(x):insert(nums[i])cost[x - 1] get_cost()# Sliding windowfor i in range(x, n):insert(nums[i])erase(nums[i - x])cost[i] get_cost()# Step 2: Dynamic Programming# dp[i][j] min operations to select j non-overlapping subarrays from first i elementsdp [[INF] * (k 1) for _ in range(n 1)]dp[0][0] 0for i in range(1, n 1):for j in range(k 1):dp[i][j] dp[i - 1][j]if i x and j 1 and cost[i - 1] INF:dp[i][j] min(dp[i][j], dp[i - x][j - 1] cost[i - 1])return dp[n][k]---复杂度分析项目 复杂度时间 O(n log x · k) — 滑动窗口 O(n log x)DP O(nk)空间 O(n x nk) — cost 数组 O(n)对顶堆 O(x)DP 数组 O(nk)由于 k ≤ 15nk 最大约为 1.5 × 10⁶空间可接受。---下载链接[LeetCode3505.py](sandbox:///mnt/agents/output/LeetCode3505.py)