以下是 LeetCode 3505. 使 K 个子数组内元素相等的最少操作数的 Java 实现---思路概述本题是 LeetCode 462最小操作次数使数组元素相等 II和 LeetCode 480滑动窗口中位数的结合题。核心思路1. 中位数贪心对于一个子数组要使其所有元素相等且操作次数最少最终值应取子数组的中位数。证明可参考 LeetCode 462。2. 滑动窗口中位数用对顶堆两个 TreeMap 模拟堆 延迟删除策略维护长度为 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]---完整 Java 代码javaimport java.util.*;class Solution {// 对顶堆 延迟删除维护滑动窗口中位数// 参考 LeetCode 480. 滑动窗口中位数 和 462. 最小操作次数使数组元素相等 IIstatic class DualHeap {// small: 大根堆存放较小的一半元素// large: 小根堆存放较大的一半元素中位数在堆顶private TreeMapInteger, Integer small;private TreeMapInteger, Integer large;private int smallSize, largeSize; // 实际有效元素个数private long smallSum, largeSum; // 元素之和private MapInteger, Integer delayed; // 延迟删除的哈希表private int smallTarget, largeTarget; // 目标大小public DualHeap(int k) {small new TreeMap(Collections.reverseOrder()); // 大根堆large new TreeMap(); // 小根堆delayed new HashMap();// small 放 floor(k/2) 个large 放 ceil(k/2) 个// 这样中位数就是 large.firstKey()smallTarget k / 2;largeTarget k - smallTarget;}// 插入元素public void insert(int num) {if (small.isEmpty() || num small.firstKey()) {small.merge(num, 1, Integer::sum);smallSum num;smallSize;} else {large.merge(num, 1, Integer::sum);largeSum num;largeSize;}makeBalance();}// 删除元素延迟删除public void erase(int num) {delayed.merge(num, 1, Integer::sum);if (!small.isEmpty() num small.firstKey()) {smallSize--;smallSum - num;if (num small.firstKey()) {pruneSmall();}} else {largeSize--;largeSum - num;if (!large.isEmpty() num large.firstKey()) {pruneLarge();}}makeBalance();}// 获取中位数large 的最小元素public int getMedian() {return large.firstKey();}// 计算当前窗口变为全部相等中位数所需的操作次数public long getCost() {int median getMedian();// small 中的元素需要增加到 medianlong cost1 (long) median * smallSize - smallSum;// large 中的元素需要减少到 medianlong cost2 largeSum - (long) median * largeSize;return cost1 cost2;}// 平衡两个堆的大小private void makeBalance() {// small 太大将最大元素移到 largeif (smallSize smallTarget) {int num small.firstKey();int cnt small.get(num);if (cnt 1) small.remove(num);else small.put(num, cnt - 1);smallSum - num;smallSize--;large.merge(num, 1, Integer::sum);largeSum num;largeSize;pruneSmall();}// large 太大将最小元素移到 smallelse if (largeSize largeTarget) {int num large.firstKey();int cnt large.get(num);if (cnt 1) large.remove(num);else large.put(num, cnt - 1);largeSum - num;largeSize--;small.merge(num, 1, Integer::sum);smallSum num;smallSize;pruneLarge();}}// 清理 small 堆顶的延迟删除元素private void pruneSmall() {while (!small.isEmpty()) {int num small.firstKey();if (delayed.getOrDefault(num, 0) 0) {delayed.put(num, delayed.get(num) - 1);if (delayed.get(num) 0) delayed.remove(num);int cnt small.get(num);if (cnt 1) small.remove(num);else small.put(num, cnt - 1);} else {break;}}}// 清理 large 堆顶的延迟删除元素private void pruneLarge() {while (!large.isEmpty()) {int num large.firstKey();if (delayed.getOrDefault(num, 0) 0) {delayed.put(num, delayed.get(num) - 1);if (delayed.get(num) 0) delayed.remove(num);int cnt large.get(num);if (cnt 1) large.remove(num);else large.put(num, cnt - 1);} else {break;}}}}public long minOperations(int[] nums, int x, int k) {int n nums.length;long INF (long) 1e18;// Step 1: 预处理 cost[i]// cost[i] 表示子数组 nums[i-x1..i]长度为x全部变为相等的最小操作数long[] cost new long[n];Arrays.fill(cost, INF);DualHeap dh new DualHeap(x);// 初始化第一个窗口 [0, x-1]for (int i 0; i x; i) {dh.insert(nums[i]);}cost[x - 1] dh.getCost();// 滑动窗口for (int i x; i n; i) {dh.insert(nums[i]); // 右端加入新元素dh.erase(nums[i - x]); // 左端删除旧元素cost[i] dh.getCost();}// Step 2: 动态规划// dp[i][j] 考虑前 i 个元素0..i-1选出 j 个不重叠的长度为x的子数组的最小操作数// 转移// 1. 不选以 i-1 结尾的子数组: dp[i][j] dp[i-1][j]// 2. 选以 i-1 结尾的子数组: dp[i][j] dp[i-x][j-1] cost[i-1]long[][] dp new long[n 1][k 1];for (int i 0; i n; i) {Arrays.fill(dp[i], INF);}dp[0][0] 0;for (int i 1; i n; i) {for (int j 0; j k; j) {// 情况1: 不选以 i-1 为结尾的子数组dp[i][j] dp[i - 1][j];// 情况2: 选以 i-1 为结尾的子数组if (i x j 1 cost[i - 1] INF) {dp[i][j] Math.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.java](sandbox:///mnt/agents/output/LeetCode3505.java)