这是一道经典的“滑动窗口 动态维护第 K 小元素”的算法题。 核心思路分析1. 题意转化根据题意数组的第一个元素 nums[0] 必然作为第一个子数组的起点其代价 nums[0] 是必选的。我们需要在剩下的元素中选出 k-1 个子数组的起点且这 k-1 个起点的下标与第二个子数组起点的下标距离不能超过 dist。2. 滑动窗口这等价于在一个大小固定为 dist 1 的滑动窗口中寻找最小的 k-1 个元素之和。3. 数据结构选择由于窗口在滑动过程中需要频繁地插入新元素、删除旧元素并动态维护前 k-1 小的元素之和我们可以使用两个 TreeMap有序集合来模拟“对顶堆”- left存储当前窗口中最小的 k-1 个元素。- right存储窗口中剩余的元素。- 同时维护一个变量 sum 记录 left 中所有元素的和以便在 O(1) 时间内获取当前窗口的最小代价。☕ Java 代码实现import java.util.TreeMap;class Solution {// left 存储滑动窗口中最小的 k-1 个数private final TreeMapInteger, Integer left new TreeMap();// right 存储滑动窗口中剩余的数private final TreeMapInteger, Integer right new TreeMap();// sum 记录 left 中所有元素的和private long sum;// leftSize 记录 left 中元素的总个数 (考虑了 value 中的计数)private int leftSize;public long minimumCost(int[] nums, int k, int dist) {// 因为 nums[0] 必选我们还需要选 k-1 个数// 所以将 k 减 1后续逻辑中的 k 即代表需要在滑动窗口中选出的数的个数k - 1;// 初始化 sum 为 nums[0] (必选代价)sum nums[0];left.clear();right.clear();leftSize 0;// 1. 初始化窗口处理前 dist 1 个元素 (nums[1] ... nums[dist1])// 先把所有元素一股脑加进 leftfor (int i 1; i dist 1; i) {add(left, nums[i]);leftSize;sum nums[i];}// 如果 left 中的元素超过了 k 个把最大的移到 right直到只剩 k 个// 这样初始化后left 里就是窗口内最小的 k 个数while (leftSize k) {moveLeftToRight();}// 记录当前最小代价long ans sum;// 2. 开始滑动窗口// i 代表新进入窗口的元素索引for (int i dist 2; i nums.length; i) {// out 是要滑出窗口的元素int out nums[i - dist - 1];// 移除 outif (contains(left, out)) {remove(left, out);leftSize--;sum - out;} else {remove(right, out);}// in 是新进入窗口的元素int in nums[i];// 决定把 in 加到哪里if (leftSize 0) {// 防御性编程如果 left 为空直接加 rightadd(right, in);} else {// 如果 in 比 left 中最大的数还小说明它有资格进入 Top Kint leftMax left.lastKey();if (in leftMax) {add(left, in);leftSize;sum in;} else {add(right, in);}}// 再平衡确保 left 中恰好有 k 个数// 情况 1: left 不够 k 个 (可能是刚才移除了一个 left 中的元素而新加的进了 right)while (leftSize k) {moveRightToLeft();}// 情况 2: left 超过 k 个 (可能是刚才移除了 right 中的元素而新加的进了 left)while (leftSize k) {moveLeftToRight();}// 更新全局最小代价ans Math.min(ans, sum);}return ans;}// 将 left 中最大的元素移动到 rightprivate void moveLeftToRight() {int x left.lastKey();remove(left, x);leftSize--;sum - x;add(right, x);}// 将 right 中最小的元素移动到 leftprivate void moveRightToLeft() {int x right.firstKey();remove(right, x);add(left, x);leftSize;sum x;}// 辅助向 TreeMap 添加元素private void add(TreeMapInteger, Integer mp, int x) {mp.merge(x, 1, Integer::sum);}// 辅助从 TreeMap 移除元素private void remove(TreeMapInteger, Integer mp, int x) {int c mp.get(x);if (c 1) {mp.remove(x);} else {mp.put(x, c - 1);}}// 辅助检查是否存在private boolean contains(TreeMapInteger, Integer mp, int x) {return mp.containsKey(x);}} 复杂度分析- 时间复杂度O(n log n)。滑动窗口遍历数组需要 O(n)每次窗口滑动时TreeMap 的插入、删除和获取最大/最小值操作均需要 O(log n) 的时间。- 空间复杂度O(n)。TreeMap 最多需要存储滑动窗口内的 dist 1 个元素在最坏情况下空间开销为 O(n)。