企业官网建设流程全解析

做一遍力扣第3013题《将数组分成最小总代价的子数组 II》，我的第一反应是“终于有个不是套模板的每日一题了”。光看标题以为又是常见的划分DP，实际操作下来才发现，它把“数组分段”包装成了“滑窗里取前k小”，底层还得靠双堆动态维护。这种题目做一遍，等于把滑动窗口、贪心、堆这三个高频考点一次性复习完，性价比相当高。

这道题比较适合两类人看：一是还在被“分割数组”类题目劝退的刷题新手，想找一道能把包装拆掉的题练手；二是已经会双堆模板，但想知道“为什么偏偏能用双堆”的进阶玩家。下面我把从题意拆解到代码实现的完整思路写一遍，顺带记录几个我实际提交时踩过的坑。

1. 拆题：这道题到底在考什么

1.1 题面先翻译成人话

题面的设定看着挺唬人：给定数组nums和两个整数k、dist，要求把数组切成恰好k个非空连续子数组，每个子数组的代价定义为该子数组第一个元素的值，总代价是所有子数组第一个元素值之和，目标是让总代价最小。

第一段必须从下标 0 开始，这一点很关键，它把nums[0]直接固定成了必选项。剩下的操作，其实就是从1到n-1之间挑出k-1个位置，作为后面每一段子数组的起点。题面里还有一个容易让人绕进去的限制：这k-1个起点的跨度不能超过dist。我这里就按“下标跨度不超过 dist”来理解，也就是任意两个被选中的起点，它们下标之差的最大值要小于等于dist。

这里建议每个做题的人先停两秒，把自己拿到的原题里的dist表达确认清楚。有的版本说的是差值上限，有的版本可能说的是包含端点后的区间宽度，这两个表述会让代码里的窗口宽度差 1。我下面给出的代码统一用“跨度不超过dist，窗口实际容纳dist+1个下标”这个口径。

1.2 等价转化：选点问题

一旦接受“每个子数组的代价只看第一个元素”，这道题就从“分段”变成了“选点”。

整个数组分段的代价，等于nums[0]加上选中的k-1个起点位置的值。子数组内部有多少元素、元素值是大是小，都对代价没有任何影响。所以问题被拆成了两层：

• 第一层：找出所有满足跨度限制的下标区间，也就是所有可能的“窗口”。
• 第二层：在每个窗口里，选出值最小的k-1个下标，把它们的值加起来，再加上nums[0]，取全局最小。

这个转化最大的好处，是让我们不再关心“分段”这个动作，问题变成了一个纯粹的“区间内取最小若干个元素”问题。后面所有解法都建立在这一点上，所以这里值得反复确认：如果不是这个转化，而是要去考虑每个子数组内部的元素，那这道题会瞬间变成一个完全不同、也复杂得多的题目。

1.3 数据范围决定算法方向

力扣把这道题放在比较靠后的位置，数据范围不会小。按常见约束来估计，n能到10^5甚至更大，k也可能接近n，dist同样可能很大。

在这种数据规模下，有几条路基本是走不通的：

• 枚举所有可能选点集合，再检查跨度是否合法，这是组合数级别，完全不可行。
• 只对每个窗口排序后取前k-1个值，窗口数量加上排序复杂度，最坏会到O(n * dist log dist)，同样会超时。
• 印象里还有一种从划分出发的区间 DP 思路，转移时枚举上一个分割点，复杂度O(n * k)，当k接近n时就是10^10级别，也扛不住。

所以目标很明确：我们需要一种能在O(log k)时间内完成窗口内“取前k-1小元素和”操作的数据结构。这个需求指向的就是堆，准确说是双堆。

2. 从暴力到滑窗的推理过程

2.1 先推一版朴素做法找感觉

不急着上双堆，我们先推一个没有任何优化的版本，用来理解窗口本身在干什么。

假设我们已经固定了一个窗口，里面包含若干个候选下标。因为要选k-1个起点，而且每个起点的代价是独立的，所以在一个窗口内部，我们没有任何理由去选“值更大”的那个起点。换句话说，给定窗口，答案是确定的：这个窗口里所有候选下标的值排序后，最小的k-1个元素之和，就是该窗口内的最优选择。

这样问题就变成了：枚举所有跨度不超过dist的窗口，每个窗口都要能快速取出最小k-1个元素的和。窗口一直在从左往右滑动，每次只移出一个元素、加入一个新元素，如果每次都对窗口内所有元素重新排序，那就太浪费了。我们要的是“增量式维护”。

2.2 为什么窗口内可以无脑贪心

这里有个看起来简单但值得确认的点：为什么窗口内直接选最小的k-1个就是对的？会不会因为某些窗口在后续滑动中还能提供更好的组合？

因为每个起点一旦被选中，它对总代价的贡献就只是一个单纯的值，和它周围选了谁、没选谁完全没有关系。这就像买东西时每件商品价格独立、不捆绑销售，预算固定时当然直接挑最便宜的几件。窗口只是划定了一个购买范围，范围里的商品价格互不影响，所以“每次选最便宜的”就是最优解。

这种“贡献独立”的性质，是整道题能够用贪心的根基。如果题目变成“每个子数组的代价和子数组长度有关”或者“相邻子数组之间有额外耦合代价”，那这个贪心立刻失效。

2.3 单一堆不够，双堆才有资格

需求已经变成：维护一个动态集合，支持增删元素，同时快速查询“最小的k-1个元素之和”。

如果只用一个小根堆，取最小值确实方便，但“删掉某个不在堆顶的元素”就很麻烦。如果只用一个大根堆，我们能快速拿到最大值，但取整体最小值做不到。单一堆解决不了“既要能拿最小，又要把过大的踢出去”这个矛盾。

双堆的思路很直接：把窗口里的元素分成两拨，一拨是“选中的最小的k-1个”，另一拨是“没被选中的其余元素”。选中的那一拨用大根堆来存，这样堆顶就是它们之中最大的那个位置；没选中的用最小堆来存，堆顶就是备选元素里最小的那个位置。只要保证“选中堆里最大的元素 <= 备选堆里最小的元素”，那么选中堆里的k-1个元素，就是整个窗口内最小的k-1个。

每滑一次窗口，最多涉及一个删除和一个插入，双堆之间通过少量搬移就能恢复上面的有序性。这也是这类题最常见的模板：用两个堆动态维护“前 k 小元素之和”。

3. 双堆滑窗的完整实现

3.1 两个堆的分工和维护规则

我给两个堆起名叫做small和large，含义如下：

• small：大根堆，实际存储时压入(-value, index)，里面保存当前窗口里被选中的k-1个元素。堆顶是选中元素里值最大的那个，方便我们随时把“最不该选”的元素踢出去。
• large：小根堆，存储(value, index)，保存当前窗口里没被选中的其余元素。堆顶是备选元素里值最小的那个，方便我们随时把“最值得选”的元素补进来。
• sum_small：记录small堆里所有元素的和。这个变量就是我们在每个窗口里想要的“前k-1个元素之和”。

维护规则可以总结成三条：

1. 数量不足时，从large的最小值搬到small。
2. 数量过多时，从small的最大值搬回large。
3. 数量恰好时，检查边界：如果small的最大值比large的最小值还要大，就交换这两个元素。

用 Python 的话，堆不支持删除堆中任意元素，所以删除时要采用“懒删除”策略：先记录某个下标已经被删除，真正需要取堆顶时，再把堆顶所有带删除标记的元素弹掉。这里需要一张belong表记录每个下标当前属于哪个堆，因为同一个值可能重复出现，不能只靠数值判断归属。

3.2 Python 完整实现与关键注释

下面这个版本我实际手测过几组数据，结构上做了比较完整的懒删除处理。代码风格是按力扣Solution来的，可以直接粘贴到编辑器里跑。

import heapq from collections import defaultdict from math import inf class Solution: def minimumCost(self, nums: list[int], k: int, dist: int) -> int: n = len(nums) if k == 1: return nums[0] # 窗口里最多只能放下 dist+1 个候选下标 if dist + 1 < k - 1: return -1 small = [] # 大根堆：(-val, idx)，存放选中的 k-1 个元素 large = [] # 小根堆：(val, idx)，存放备选元素 belong = [0] * n # 0 表示在 large 或未激活，1 表示在 small dead_small = defaultdict(int) dead_large = defaultdict(int) small_size = 0 sum_small = 0 def clean(): # 清除两个堆顶的“已删除”元素 while small and dead_small[small[0][1]] > 0: idx = small[0][1] dead_small[idx] -= 1 heapq.heappop(small) while large and dead_large[large[0][1]] > 0: idx = large[0][1] dead_large[idx] -= 1 heapq.heappop(large) def add_large(val, idx): belong[idx] = 0 heapq.heappush(large, (val, idx)) def remove_idx(idx): nonlocal small_size, sum_small if belong[idx] == 1: dead_small[idx] += 1 small_size -= 1 sum_small -= nums[idx] belong[idx] = -1 else: dead_large[idx] += 1 belong[idx] = -1 def balance(): nonlocal small_size, sum_small clean() # small 数量不够，从 large 里补最小的 while small_size < k - 1 and large: clean() val, idx = heapq.heappop(large) belong[idx] = 1 heapq.heappush(small, (-val, idx)) small_size += 1 sum_small += val # small 数量过多，把最大的放回 large while small_size > k - 1 and small: clean() neg_val, idx = heapq.heappop(small) belong[idx] = 0 heapq.heappush(large, (-neg_val, idx)) small_size -= 1 sum_small -= -neg_val # 边界修正：如果选中的最大值反而比备选的最小值大，就交换 while True: clean() if not small or not large or -small[0][0] <= large[0][0]: break neg_val, idx_s = heapq.heappop(small) val, idx_l = heapq.heappop(large) belong[idx_s] = 0 belong[idx_l] = 1 small_size -= 1 sum_small -= -neg_val heapq.heappush(large, (-neg_val, idx_s)) small_size += 1 sum_small += val heapq.heappush(small, (-val, idx_l)) # 初始窗口为 [1, min(dist + 1, n - 1)] right = min(dist + 1, n - 1) for i in range(1, right + 1): add_large(nums[i], i) balance() ans = inf if small_size == k - 1: ans = nums[0] + sum_small # 窗口右端点向右移动，左端点同步右移 for r in range(right + 1, n): l = r - dist - 1 remove_idx(l) add_large(nums[r], r) balance() if small_size == k - 1: ans = min(ans, nums[0] + sum_small) return ans if ans != inf else -1

我把容易写错的几行单独拎出来说。

初始化时right = min(dist + 1, n - 1)，因为窗口跨度是dist，能容纳的下标个数就是dist + 1。如果题目里的dist表达的是“区间内元素个数”，这里就要改成right = min(dist, n - 1)，这是最典型的 off-by-one 来源。

窗口滑动时，l = r - dist - 1也经常被写成r - dist。你可以用一个很小的例子验证：初始窗口是[1, right]，第一次滑入r = right + 1后，新窗口应该是[2, right + 1]，所以移除的是下标 1。而r - dist - 1 = (right + 1) - dist - 1，由于right = dist + 1，正好等于 1。

懒删除那一块尤其要注意：删除small里的元素时，不能只标记，还必须立刻把sum_small减掉，否则后面的答案全错。我用belong数组来判断元素归属，比用值判断安全得多，因为数组里经常有重复元素。

3.3 另一个写法：简洁但不太通用的 multiset 版

如果是在支持平衡树的语言里，比如 C++，双堆的“边界交换”逻辑会被multiset天然吸收。它本质上是一个能增删、能查前后继的有序集合，维护前k-1小非常直接。

class Solution { public: long long minimumCost(vector<int>& nums, int k, int dist) { int n = nums.size(); if (k == 1) return nums[0]; if (dist + 1 < k - 1) return -1; multiset<int> left, right; // left 保存选中的 k-1 个最小值，right 保存其余 long long sumLeft = 0; auto rebalance = [&]() { while (left.size() < k - 1 && !right.empty()) { auto it = right.begin(); sumLeft += *it; left.insert(*it); right.erase(it); } while (left.size() > k - 1) { auto it = prev(left.end()); sumLeft -= *it; right.insert(*it); left.erase(it); } while (!left.empty() && !right.empty() && *prev(left.end()) > *right.begin()) { int a = *prev(left.end()); int b = *right.begin(); sumLeft += b - a; left.erase(prev(left.end())); right.erase(right.begin()); left.insert(b); right.insert(a); } }; auto add = [&](int x) { right.insert(x); rebalance(); }; auto remove = [&](int x) { auto it = left.find(x); if (it != left.end()) { sumLeft -= x; left.erase(it); } else { right.erase(right.find(x)); } rebalance(); }; int R = min(dist + 1, n - 1); for (int i = 1; i <= R; ++i) add(nums[i]); long long ans = LLONG_MAX; if (left.size() == k - 1) ans = nums[0] + sumLeft; for (int r = R + 1; r < n; ++r) { remove(nums[r - dist - 1]); add(nums[r]); if (left.size() == k - 1) ans = min(ans, nums[0] + sumLeft); } return ans == LLONG_MAX ? -1 : ans; } };

这个写法虽然短，但有个小坑：multiset的remove要用find定位再erase，如果你直接用erase(x)，它会一次性把所有等于x的元素全删掉。窗口里可能存在多个相同值，那样就会伤及无辜。所以我代码里特意写了left.find(x)和right.find(x)。

4. 边界条件、踩坑与验证

4.1 最容易写错的三个地方

第一，下标差与窗口宽度的关系。我最开始写代码时默认窗口长度 = dist，结果样例里第一个窗口就漏了一个元素。用dist表示跨度时，窗口实际容纳的元素是dist + 1，这点必须靠手算一个小例子才能彻底记住。

第二，k == 1的特判。k等于 1 的时候不需要选任何分割点，整个数组就是一段，答案直接是nums[0]。如果漏掉这个分支，后面计算k-1就会变成 0，代码在窗口里会不停尝试把small_size补到 0，虽然不会崩，但边界交换逻辑会变得很奇怪。

第三，懒删除标记没有和计数同步。Python 双堆版本里，每次从small堆删除元素时，除了要设置dead_small标记，还得立刻更新small_size和sum_small。我第一版漏了sum_small的更新，导致前几个窗口的答案看起来正常，滑动几步后突然出现一个特别离谱的大数，这种 bug 排查起来非常折磨人。

4.2 手玩几组测试数据

拿一组能直观验证的例子过一遍：

nums = [3, 2, 1, 4, 5]，k = 3，dist = 1。

答案应该是 6。因为k-1 = 2，跨度 1 的窗口最多只有两个候选下标，可用的也就是下标 1 和 2，值是 2 和 1，nums[0] + 2 + 1 = 6。如果窗口扩展成全范围，反而可能选到更大的值，所以 6 就是最优。这个例子用来验证代码里的right = dist + 1很合适。

另一组是重复值场景：

nums = [5, 2, 2, 3, 4]，k = 2，dist = 3。

nums[0] = 5，窗口跨度 3 的情况下，第一个窗口覆盖下标 1 到 4，选中最小的那个 2，答案 7。全程有多个相同的 2，双堆的重复值处理就得靠下标而不是值本身来判断，这正好可以测试belong表的正确性。

还有一个不能不测的无解场景：

nums = [1, 2, 3, 4]，k = 4，dist = 0。

此时dist + 1 = 1，窗口最多只能放一个候选下标，但我们需要k-1 = 3个，直接返回 -1。

4.3 复杂度与真实表现

时间复杂度是O(n log k)。每个下标进入窗口后最多经历“进入 large、可能搬进 small、可能又被搬回 large、最后被标记删除”这么几轮，每轮都是堆操作，log k的代价。空间复杂度是O(n + k)，belong表需要记录每个下标的状态，两个堆一共最多保存窗口内dist+1个元素。

实际提交表现上，Python 版本因为有懒删除的while clean逻辑，常数会比 C++ 版本大一些，但在n = 10^5这个量级依然可以稳定通过。建议自己实现时在本地多测几组随机数据对比暴力答案，尤其是 sliding window 的边界，这样能快速定位 off-by-one。

这类题目做多了以后，我的习惯是先花一分钟把题目里的限制条件翻译成数据结构的操作：dist对应的是窗口宽度，k-1对应的是堆里要维护的数量，nums[i]对应的是元素的优先级。翻译完成之后，整道题就从“数组分段”变成了“滑窗取前 k 小”，整个过程顺理成章。