LeetCode 3013 — 将数组分成最小总代价的子数组 II题意速览数组切成k 个连续子数组代价 各子数组首元素之和第 1 个子数组必从index 0开始 ⇒nums[0]固定计入答案还需在nums[1..n-1]中选k-1 个起点i₁ i₂ … iₖ₋₁约束iₖ₋₁ − i₁ ≤ dist⇒ 所有 k-1 个起点必须落在某个长度为 dist1 的连续区间内目标最小化nums[0] nums[i₁] … nums[iₖ₋₁]核心转化在nums[1…n-1]上滑一个长度为dist1的窗口每个窗口位置上贪心取最小的 k-1 个值作为起点值越小代价越小全局取最小。为什么贪心成立—— 一旦窗口决定了起点们允许的索引范围你想让那些起点的nums值之和最小当然选范围内最小的 k-1 个数对应的位置当切割点。✅ JavaScript 实现Fenwick Tree 坐标压缩O(n log n)var minimumCost function(nums, k, dist) { const n nums.length; const need k - 1; // 需要从 nums[1..] 中选几个起点 const offset 1; // 窗口滑过 nums[1..n-1] 中的位置 // ---------- 坐标压缩 ---------- const uniq [...new Set(nums)].sort((a, b) a - b); const rank new Map(); uniq.forEach((v, i) rank.set(v, i 1)); const M uniq.length; // ---------- Fenwick Tree两个计数 加权和 ---------- const cnt new Array(M 1).fill(0); const sum new Array(M 1).fill(0); // 用普通 number总和 ≤ 1e14 在安全范围内 const lowbit x x -x; const add (r, dc, dv) { for (; r M; r lowbit(r)) { cnt[r] dc; sum[r] dv; } }; // 前缀计数 const prefixCnt r { let s 0; for (; r 0; r - lowbit(r)) s cnt[r]; return s; }; // 前缀和 const prefixSum r { let s 0; for (; r 0; r - lowbit(r)) s sum[r]; return s; }; // 计算当前窗口中「最小的 need 个数的总和」 const windowSmallestSum () { // 二分找第 need 小的元素所在 rank let lo 1, hi M; while (lo hi) { const mid (lo hi) 1; if (prefixCnt(mid) need) hi mid; else lo mid 1; } const r lo; // 第 need 小所在的 rank const cntBefore prefixCnt(r - 1); const sumBefore prefixSum(r - 1); const val uniq[r - 1]; const takeFromThisRank need - cntBefore; // 在 uniq[r-1] 这个值里取几个 return sumBefore takeFromThisRank * val; }; // ---------- 滑动窗口 ---------- // 初始窗口覆盖 nums[1] ~ nums[dist1]即索引 1..dist1 const winSize dist 1; for (let i 1; i winSize i n; i) { add(rank.get(nums[i]), 1, nums[i]); } let ans windowSmallestSum(); // 窗口右滑移出 nums[start]移入 nums[startwinSize]start 从 1 开始 for (let start 1; start winSize n; start) { // 移出 nums[start]即窗口最左 add(rank.get(nums[start]), -1, -nums[start]); // 移入 nums[start winSize] add(rank.get(nums[start winSize]), 1, nums[start winSize]); ans Math.min(ans, windowSmallestSum()); } return nums[0] ans; };关键步骤图解以nums [1,3,2,6,4,2], k3, dist3为例索引: 0 1 2 3 4 5 nums: [1] [3] [2] [6] [4] [2] ↑固定 ───────────────────── 起点候选在索引 {1,2,3,4,5} 中选 k-12 个 窗口长度 dist1 4 窗口① 覆盖 {1,2,3,4} → 值 {3,2,6,4} → 最小2个 235 窗口② 覆盖 {2,3,4,5} → 值 {2,6,4,2} → 最小2个 224 ← 但注意这些值是不同位置的等一下——窗口②的最小值是 2(索引2) 和 2(索引5)但索引 2 和 5 不在同一窗口{2,3,4,5}吗是的它们在2和5都在窗口内。但窗口内最小的两个值是nums[2]2和nums[5]2和为 4……但答案是 5 不是145吗nums[0]45。哦对145也等于 5。窗口②的两个最小是nums[2]2和nums[5]2和 4总代价 14 5。✅复杂度时间O(n log n) — 坐标压缩排序 每个滑动步 O(log n) 二分 × 2次前缀查询空间O(n) — 压缩表 两个 BIT 数组为什么 BIT 选值而不是存索引因为我们只关心值的大小选最小 k-1 个坐标压缩后用 BIT 按 rank 统计有多少个值 ≤ X以及这些值的和是多少天然支持动态增删窗口滑出删一个、滑入加一个和找最小的 k 个的和。如果你想用两个堆/有序集合的思路C 的multiset写法JS 里需要自己实现平衡 BST 或用 npm 的sortedcontainers替代品Fenwick 方案在纯 JS 环境下最自给自足。