今天刷每日一题刷到了 3013，题号带个 II 就说明事情不简单。这道题把“划分型 DP”和“单调栈 + 懒标记线段树”焊死在了一起，而且线段树里维护的还不是普通区间最值，是一组会随着右端点移动而整体变化的候选值。如果你对这类结构不熟，第一次见会觉得代码像魔法；但把其中的“为什么”拆开之后，会发现它其实是很多 Hard 题共用的一套骨架。这篇就按我实际调试的顺序来写，从暴力 DP 开始，一直讲到能过大数据版本的完整实现，最后附上我踩过的几个坑。适合已经会基础 DP、想进阶单调栈优化的读者，也适合准备面试时专门补一补“数据结构优化 DP”这类套路的同学。
1. 题目解读与核心思路
1.1 题意与本质
题目给一个数组，要求把它切分成若干个连续的子数组。每个子数组的代价定义成这个子数组里的最大值，所有子数组的代价之和就是总代价，目标是让这个总代价最小。有的版本里还会带一个正整数 k，要求每段长度不能超过 k；如果题面没有这个参数，就等价于 k 无限大。
这道题的难点不在于看懂题意，而在于看穿它的规模。I 版本的数据可能允许 O(nk) 的复杂度，II 版本直接把 n 拉到 1e5 甚至更大，再想靠枚举最后一段的起点来转移，基本死路一条。题目名字里反复强调的“子数组 II”，真正含义是：你必须找到一个跟 k 无关、只跟 n 的规模相关的做法。
我第一眼的感觉是：这题肯定跟“最大值”贡献有关，因为一段的代价只取最大值，最小的元素放在哪里都不会影响这段的代价。这种“取最大值”的性质，天然适合用单调栈去管理“左端点往左移动时，最大值分段变化”的过程。
1.2 为什么暴力 DP 过不了
先别急着上数据结构，把暴力版本写出来能帮我们看清楚优化的方向。定义 dp[i] 表示前 i 个元素已经完成划分时的最小总代价，dp[0] = 0。计算 dp[i] 时，最后一段一定是从某个 j 开始、到 i - 1 结束（这里下标按数组从 0 开始算），转移是：
dp[i] = min( dp[j] + max(nums[j..i-1]) )
如果带 k 限制，j 的范围还要满足 i - j ≤ k，也就是 j ≥ i - k。直接枚举 j，每次再算区间最大值，复杂度是 O(n^2) 甚至 O(n^2 log n)。I 版本数据小，这样糊上去可能还能过；II 版本遇到 n = 1e5，平方复杂度直接就卡死了。
很多人的第一反应是套一个“滑动窗口 + 堆”之类的结构来维护最小值，但这里有个麻烦：dp[j] 是固定的，而 max(nums[j..i-1]) 会随着右端点 i 的移动而变化，而且这个变化不是“每个元素独立变化”，是整个区间一批一批地统一变化。这种结构用堆很难维护，需要用单调栈把它拆成若干段，再用线段树做区间加。
2. DP 方程与单调栈优化
2.1 从朴素 DP 出发
把上面的转移换个写法。固定当前的右端点 i，把所有候选的左端点 j 看成线段树上的叶子节点，叶子 j 存一个候选值：
candidate(j) = dp[j] + max(nums[j..i-1])
那么 dp[i] 就是所有合法叶子候选值的最小值。随着右端点 i 每次增加一格，会发生两件事：
第一，新增了一个叶子节点 i，它的候选值初始是 dp[i] + 0，因为“从 i 开始到当前右端点（还没有新增前）”这段是空的，最大值按 0 处理。
第二，所有已有叶子 j（j < i）对应的 max(nums[j..i-1]) 都可能变大，因为区间右端加入了新的数 nums[i-1]。
暴力做法是逐个更新所有叶子，太慢。但如果能观察到“max 变大”这件事具有区间性，就可以批量更新。
2.2 最大值贡献的“区间性”
任取一个右端点 i，让左端点 j 从 i 开始往左走。区间 nums[j..i-1] 的长度越来越大，最大值怎么变？它只会单调不降，而且不是每个位置变一次，是一段一段地跳变。
举个具体例子，数组是 [2, 5, 3, 1]，假设当前右端点指向最后一个元素 1，从右往左看：
- j = 3，区间 [1]，最大值 1
- j = 2，区间 [3, 1]，最大值 3
- j = 1，区间 [5, 3, 1]，最大值 5
- j = 0，区间 [2, 5, 3, 1]，最大值 5
左端点从 3 到 0，最大值分别是 1、3、5、5。连续的一段左端点共享同一个最大值：比如 j = 0 和 j = 1 都对应最大值 5。
现在把右端点继续向右扩，新增一个比较大的数，比如数组变成 [2, 5, 3, 1, 4]，右端点是 4。从右往左看：
- j = 4，区间 [4]，最大值 4
- j = 3，区间 [1, 4]，最大值 4
- j = 2，区间 [3, 1, 4]，最大值 4
- j = 1，区间 [5, 3, 1, 4]，最大值 5
- j = 0，区间 [2, 5, 3, 1, 4]，最大值 5
你会发现，原本“最大值等于 1”的那段左端点（j = 3）被新来的 4 顶掉了，变成最大值 4；原本“最大值等于 3”的那段（j = 2）也被 4 顶掉了；但 j = 0 和 j = 1 的最大值还是 5，因为 5 仍然比 4 大。
这就是单调栈登场的原因：每次加入新数 x，只会把“当前最大值 ≤ x”的那些连续候选段整体提升到 x，而那些当前最大值已经大于 x 的段完全不用动。
2.3 单调栈维护最大值分段
维护一个单调递减的栈，栈里每个元素是一个三元组 (l, r, val)，表示当前右端点下，左端点在 [l, r] 范围内的所有候选叶子，它们对应的区间最大值都是 val。栈中 val 从栈底到栈顶严格递减。
每处理一个新的 nums[i]，先把新候选位置 i 加入线段树，再把栈里所有 val ≤ nums[i] 的节点依次弹出。每弹出一个节点，说明这个节点覆盖的左端点区间 [l, r] 的“段最大值”被新数统一提升到了 nums[i]，因此线段树上要做一次区间加：把 [l, r] 上每个候选值的增量加上 nums[i] - val。
弹完之后，把所有被弹出区间的左边界合并到一起，再加上新位置 i，一起压成一个新节点 (last, i, nums[i])。比如刚才的例子，新数 4 把原来的 [3,3] 和 [2,2] 两个节点都弹掉了，最后压入的节点就是 [2, 4]，它们的最大值当前都是 4。
这套操作本质上是在动态维护“向右扩展一个元素时，所有左端点候选值的变化量”。单调栈保证了每个节点最多被创建一次、被弹出一次，弹出一共发生 O(n) 次；每次弹出对应一次线段树区间加，总复杂度就有了保障。
3. 线段树落地：候选值与区间维护
3.1 线段树里存的是什么
很多题解说到“线段树维护候选值”就一笔带过了，实际动手时会卡住。这里明确一下：线段树的下标就是左端点 j，叶子 j 存的是 dp[j] + 当前右端点下 max(nums[j..i-1]) 的值。查询时，直接取一段区间的最小值，就能得到 dp[i]。
因此线段树需要支持三种操作：
- 单点赋值：把叶子 i 设置成 dp[i]，表示新分割点加入，但它对应的“当前段最大值”暂时是 0。
- 单点加：把叶子 i 加上 nums[i]，这样它的候选值就从 dp[i] 变成 dp[i] + nums[i]，对应最后一段只包含 nums[i] 的情况。
- 区间加：单调栈弹出节点时，把 [l, r] 上所有候选值统一加上一个差值。
- 区间最小值查询：求出合法左端点范围内的最小候选值。
这里容易绕晕的是“先单点赋值再单点加”。我一开始写的时候先做区间合并，再去初始化新位置 i，结果新位置永远少加了一个 nums[i]，每次答案都偏小。原因是：位置 i 在被压入单调栈节点之前，它不在任何已有区间里，必须手动把它从“空段最大值 0”变成“包含 nums[i] 时最大值是 nums[i]”的状态。
3.2 单点赋值与区间加的配合
整体流程按右端点 i 从 0 到 n - 1 循环：
第一步，把叶子 i 单点赋值成 dp[i]。dp[i] 在上一轮已经算好了，dp[0] 手动设成 0。这个赋值的意思是：现在允许新开一段从 i 开始，这段目前是空的，所以候选值是 dp[i] + 0。
第二步，把叶子 i 单点加上 nums[i]。区间从 i 到 i 现在非空了，最大值就是 nums[i]，候选值变成 dp[i] + nums[i]。
第三步，把 nums[i] 往单调栈里塞。弹掉所有 val ≤ nums[i] 的栈顶节点，每弹一个，就在线段树上对它的 [l, r] 做区间加 nums[i] - val，同时把 last 向左合并；最后压入新节点 (last, i, nums[i])。
第四步，查询 dp[i + 1]。此时右端点已经扩展到了 i，所有叶子的候选值都对应“右端点为 i”的状态。要看最后一段的起点 j 允许落在哪个范围：如果 k 限制段长，必须满足 i - j + 1 ≤ k，也就是 j ≥ i - k + 1；如果没有 k 限制，j 从 0 开始就可以。于是查询范围是 [max(0, i - k + 1), i]，取最小值赋给 dp[i + 1]。
为什么第三步压入的新节点右边界是 i，而不是 i - 1？因为位置 i 已经在上一步被初始化成了 dp[i] + nums[i]，它和其它被弹出的区间一起，当前最大值都是 nums[i]，理应属于同一个单调栈节点。这样后面如果来了更大的数，这个节点整体被弹出时，区间加会把位置 i 也一起正确更新。
3.3 查询窗口与 K 限制
带 k 限制时，查询左边界会不断右移，那些落在窗口之外的候选叶子其实已经“过期”了。我们不需要真的把它们从线段树里删掉，只要查询时不问它们就行。为什么可以不管它们？因为左边界只会越来越大，已经滑出窗口的答案不可能再被用到，留着它们的值不会影响后续窗口内的最小值。
但这里有个细节：过期叶子仍然会收到后续的区间加更新，因为单调栈的节点区间是连续覆盖的，可能同时包含过期叶子和有效叶子。这没有关系，区间加对过期叶子多算一点也无所谓，它们永远不会被查询到。真正需要注意的是，不要把过期的叶子误算进查询范围，所以每次查询的 L 都要用 max(0, i - k + 1) 算一遍，而不是用固定的 0。
如果题目没有 k 限制，L 恒为 0，整套流程会变得更简单，线段树查询范围直接就是 [0, i]。
4. 完整代码与复杂度分析
4.1 可运行代码
下面是一份可以直接跑的 C++ 实现，线段树部分我写得比较保守，用数组开四倍空间，懒标记累加。为了看着清晰，代码里没有做太多封装。
#include <bits/stdc++.h> using namespace std; struct SegTree { int n; const long long INF = 4e18; vector<long long> mn, lazy; SegTree(int n) : n(n), mn(4 * n, INF), lazy(4 * n, 0) {} void apply(int p, long long v) { mn[p] += v; lazy[p] += v; } void push(int p) { if (lazy[p] != 0) { apply(p * 2, lazy[p]); apply(p * 2 + 1, lazy[p]); lazy[p] = 0; } } void pull(int p) { mn[p] = min(mn[p * 2], mn[p * 2 + 1]); } void add(int p, int l, int r, int ql, int qr, long long v) { if (ql <= l && r <= qr) { apply(p, v); return; } push(p); int mid = (l + r) / 2; if (ql <= mid) add(p * 2, l, mid, ql, qr, v); if (qr > mid) add(p * 2 + 1, mid + 1, r, ql, qr, v); pull(p); } void setv(int p, int l, int r, int pos, long long v) { if (l == r) { mn[p] = v; lazy[p] = 0; return; } push(p); int mid = (l + r) / 2; if (pos <= mid) setv(p * 2, l, mid, pos, v); else setv(p * 2 + 1, mid + 1, r, pos, v); pull(p); } long long query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return mn[p]; push(p); int mid = (l + r) / 2; long long res = INF; if (ql <= mid) res = min(res, query(p * 2, l, mid, ql, qr)); if (qr > mid) res = min(res, query(p * 2 + 1, mid + 1, r, ql, qr)); return res; } void range_add(int l, int r, long long v) { if (l > r) return; add(1, 0, n - 1, l, r, v); } void point_set(int pos, long long v) { setv(1, 0, n - 1, pos, v); } long long range_min(int l, int r) { return query(1, 0, n - 1, l, r); } }; long long solve(vector<int>& nums, int k) { int n = (int)nums.size(); SegTree seg(n); vector<long long> dp(n + 1, 0); struct Node { int l, r; long long val; }; vector<Node> st; for (int i = 0; i < n; ++i) { long long x = nums[i]; // 新分割点 i 加入：先当作空段，最大值贡献是 0 seg.point_set(i, dp[i]); // 空段变成只包含 nums[i] 的段，最大值贡献是 x seg.range_add(i, i, x); int last = i; while (!st.empty() && st.back().val <= x) { Node cur = st.back(); st.pop_back(); // 这个区间原来的最大值是 cur.val，现在被统一提升到 x seg.range_add(cur.l, cur.r, x - cur.val); last = cur.l; } st.push_back({last, i, x}); // 带 k 限制时，最后一段起点 j 必须满足 i - j + 1 <= k int L = max(0, i - k + 1); dp[i + 1] = seg.range_min(L, i); } return dp[n]; }如果你拿到这题时确定没有 k 限制，把 L 直接写成 0 即可。代码里线段树的下标范围是 [0, n - 1]，dp 数组长度是 n + 1，这样 dp[n] 刚好对应整个数组划分完的答案。
4.2 复杂度与空间
线段树每次操作都是 O(log n)，单调栈的每个节点最多被压入一次、弹出一次，弹出一共 O(n) 次，所以整体时间复杂度是 O(n log n)。空间上，线段树是 O(n)，单调栈也是 O(n)。
这个复杂度对 II 版本的 n = 1e5 甚至 1e6 都能轻松跑过。如果限制 k 比较小，理论上也可以尝试用“滑动窗口 + 可撤销堆”之类的结构，但通用性不如这种方案，换一道题可能就废了。
5. 常见问题与调试实录
5.1 错误一：新位置 i 没有被正确加上 nums[i]
这是我第一次跑样例就翻车的地方。如果忘记对叶子 i 做单点加 nums[i]，那么 dp[1] 就是 dp[0] + 0，永远等于 0。原因前面已经说过：位置 i 是刚加入的，它不在任何已有单调栈节点的覆盖范围内，不会因为“弹出旧节点”而获得增量，必须手动把“最大值贡献”从 0 改成 nums[i]。
同样的道理，如果你把“压入单调栈节点”这一步放在“初始化位置 i”之前，也会出问题，因为此时位置 i 还没有被纳入任何节点，后续弹出操作碰不到它。顺序必须是：先加入 i，再弹栈合并。
5.2 错误二：单调栈的比较符号写反
弹栈条件应该是栈顶 val ≤ x。因为新来的 x 会把所有“当前最大值不超过 x”的段全部吃掉，它们的最大值统一变成 x。如果你写成 val < x，那么 val 恰好等于 x 的区间不会被弹出，而是以两个相邻节点的形式共存。这不一定错，但会让栈多一层，后续逻辑变复杂，而且在某些写法下会导致重复区间加。我习惯用 ≤，把所有相等的段合并成一个节点，写起来更干净。
还有一个细节：弹栈更新区间加时，delta 是 x - cur.val，不是 x。这点很容易脑抽写错。cur.val 是这段此时的旧最大值，区间加的目的只是把旧最大值拉到 x，所以加的是差值。
5.3 错误三：查询边界和 INF 处理
带 k 限制时，查询左边界是 max(0, i - k + 1)，这个式子我在草稿上演算过多次才真正放心。因为叶子下标是最后一段的起点 j，段长度是 i - j + 1，限制段长 ≤ k，解出来 j ≥ i - k + 1。
INF 建议设成 4e18 这样的超大值，不要用 int 最大值，因为候选值里 dp[j] 和最大值都会累加，虽然题目数值一般不大，但 long long 更稳妥。线段树初始化全部是 INF，只有叶子 0 在循环前会被 set 成 dp[0] = 0，其它叶子在对应轮次才被 set。
5.4 快速自检的样板用例
调试这类题时，我一般会准备几个小用例：
- 数组 [1,2,3]，k 无限，答案应该是 3，因为整段最大值是 3，切成多段只会更差。
- 数组 [3,2,1]，答案也应该是 3，整段最大值是 3，单独切会变成 3 + 2 + 1。
- 数组 [1,3,2]，k = 2，答案应该是 4，因为整段长度 3 超过限制，最优是 [1] + [3, 2]，代价 1 + 3。
- k = 1 时，答案必须等于数组元素之和，因为每个元素只能单独成段，每段代价就是它本身。
这些用例能同时验证 DP 转移、单调栈合并、窗口边界三块逻辑。如果你跑上面这些都对了，再去跑随机数据对拍，基本就不会有大问题。
最后再分享一个我在做题时的小技巧：这道题的“单调栈维护最大值分段 + 线段树批量改候选值”的框架，抽象出来就是“每个叶子有一个基础值 dp[j]，后面又有一个会随着右端点变化的附加项，用单调栈把附加项的变化拆成区间加”。这套框架在很多 DP 优化题里都能复用，比如一些求“子数组最大值贡献总和”的题，只是查询目标和修改方式略有不同。下次再看到类似的 Hard 题，可以先往这个方向上靠一靠，大概率能省不少时间。
