LeetCode 768. 最多能完成排序的块 II

2021-09-19 HGNULB 约 13 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 768. 最多能完成排序的块 II

题意分析

给定一个整数数组 arr，把它切成若干个连续的块，对每个块各自排序后再按原顺序拼接起来，要求拼接结果恰好等于整个数组升序排序的结果。问最多能切成多少块。

「最多」这个词值得先想一层：块切得越多越好，而切分点越多约束越强。所以这不是一道搜索题，而是一道判定题——每个可能的切分点是否合法，彼此其实是独立的，把所有合法切分点全部用上就得到了最大块数。这一步认识能立刻排除掉「枚举所有切法」的方向。

什么样的位置可以切？在下标 $i$ 与 $i+1$ 之间切一刀合法，当且仅当前缀 $[0, i]$ 里的元素恰好就是排序后数组的前 $i+1$ 个元素（作为多重集合相等）。等价的、更好用的判据是：$\max(arr[0..i]) \le \min(arr[i+1..n-1])$。因为块内可以任意重排，块与块之间不能跨越，所以只要左边的最大值不超过右边的最小值，左边排完序就正好占据了排序结果的前若干位。

这道题标着 II，前一问（769 题）的数组是 $0$ 到 $n-1$ 的排列，所以「前缀最大值等于下标」就是充要条件。本题去掉了排列这个限制，元素可以重复、可以任意大，那个简洁判据立刻失效。识别出「重复元素让基于下标的判定不再成立」，是本题相对于 I 的全部新增难度。

约束是 $1 \le n \le 2000$，$0 \le arr[i] \le 10^8$。$n^2$ 是四百万，其实也能过；但值域到 $10^8$ 说明不能按值开桶。$n$ 给得小，是允许你先写出 $O(n)$ 前后缀极值的直观解法；而真正想考的单调栈解法是一次遍历、无需额外前缀数组。

边界方面：数组完全有序时每个元素自成一块，答案为 $n$；完全逆序时只能是一整块，答案为 1；全部元素相同时每个元素都能自成一块，答案为 $n$——最后这条正是重复元素的典型场景，任何把相等误判为「必须合并」的实现都会在这里翻车。

解法：单调栈合并块

核心思路

从判据出发的最直接做法是：预处理前缀最大值数组和后缀最小值数组，然后枚举每个位置 $i$，若 $preMax[i] \le sufMin[i+1]$ 就计一刀。这是正确的 $O(n)$ 解法，但它需要两次额外扫描和两个长度为 $n$ 的数组，而且必须先看到全部数据才能开始判断——是离线的。瓶颈在于：后缀最小值这个信息，本质上是在补救「我提前切了一刀，后面却冒出一个更小的数」。

换个角度：能不能一边扫一边维护「当前的切分方案」，遇到破坏性的元素就把已切的块合并回去？这就把离线的判定变成了在线的修正。

于是显式写下要维护的状态：一个栈，栈中每个元素代表一个当前已划定的块，值是该块内的最大值。栈从底到顶单调不减。 单调不减这一条是不变量，它成立的理由是：如果后一个块的最大值小于前一个块的最大值，就说明后块里存在一个比前块最大值还小的元素，它排序后必须跑到前面去，两个块就不该被切开——这样的状态在算法中会被立刻合并掉，永远不会留在栈里。

处理新元素 $x$ 时只有两种情形：

$x \ge$ 栈顶：$x$ 不小于此前所有元素（由单调性，栈顶就是全局前缀最大值），把它单独切成一个新块是合法的，直接入栈。注意这里用的是 $\ge$ 而不是 $>$，相等时也允许自成一块——因为判据只要求「左边最大值不超过右边最小值」，取等是合法的。这正是重复元素能被正确处理的关键。

$x <$ 栈顶：$x$ 比前一个块的最大值还小，排序后它必须排到那个块的位置之前，所以这一刀不能切，$x$ 必须并入前面的块。而且不止一个块——所有最大值严格大于 $x$ 的块都得跟着并进来，因为它们之间同样无法与 $x$ 分离。合并后的新块的最大值，等于被合并的所有块最大值中的最大者，也就是最先弹出的那个栈顶（由单调性，它就是最大的）。合并完把这个值压回栈中。

为什么合并时的循环条件是「栈顶严格大于 $x$」而不是「大于等于」：如果栈顶恰好等于 $x$，说明前面那个块的最大值就是 $x$，那么把 $x$ 放在新的一块里完全合法（左边最大值 $= x \le x =$ 右边最小值）。用 $\ge$ 会把本可以分开的块错误合并，答案偏小。这个不等号是本题与 I 的分水岭，全部重复元素的用例都压在它身上。

还要注意合并后不需要再和新的栈顶比较：循环退出时栈顶已经不大于 $x$，而合并后的值虽然大于 $x$，但它同样不小于当前栈顶（因为原栈单调不减，被弹出的都在更上面），压回去后单调性依然成立。

最后，答案就是栈的大小——栈中每个元素恰好对应一个最终的块。

解题步骤

第一步，准备一个空栈，栈中存放各块的最大值。 为什么只需要存最大值而不需要存块的边界或内容：判定一刀能否切下，只依赖「左侧全部元素的最大值」和「当前元素」，块内的具体成员与算法无关。把状态压缩到一个数，是这个解法简洁的根源。

第二步，顺序遍历数组，取出当前元素 $x$。

第三步，若栈为空或 $x \ge$ 栈顶，把 $x$ 压栈作为新块。 为什么栈空时直接压：第一个元素总能自成一块。为什么用 $\ge$ 而不是 $>$：相等时切开仍满足「左最大值 $\le$ 右最小值」，这是处理重复元素的核心，改成 $>$ 会让全相同数组的答案退化成 1。

第四步，否则先弹出栈顶记为 $curMax$。 为什么第一次弹出不需要比较：能进入这个分支就说明栈顶严格大于 $x$，它必然要被合并。为什么它就是合并后的最大值的初值：栈单调不减，栈顶是当前所有块最大值中最大的。

第五步，继续弹栈，只要栈非空且栈顶严格大于 $x$，就把它并入并用它更新 $curMax$。 为什么条件是严格大于：栈顶等于 $x$ 时，前一块的最大值恰好是 $x$，切开合法，不该合并。为什么要用 $\max$ 更新（尽管由单调性新弹出的必然不大于 $curMax$）：写上 $\max$ 是防御性的，也让「合并后的最大值取所有被合并块的最大者」这个语义直接可读。

第六步，把 $curMax$ 压回栈。 为什么压的是 $curMax$ 而不是 $x$：合并后的块包含了原来那些块的全部元素，它的最大值是 $curMax$（必然大于 $x$），后续元素要与这个值比较才正确。压 $x$ 会让前缀最大值凭空变小，后面本不该切的地方被切开。

第七步，遍历结束返回栈的大小。 为什么栈的大小就是答案：栈中每个元素对应一个块，且这些块覆盖了全部元素、互不重叠。

以 arr = [2, 3, 1, 4, 4] 走一遍。排序后是 [1, 2, 3, 4, 4]。

$x = 2$：栈为空，压入。栈 = [2]。当前方案是一块 {2}。

$x = 3$：$3 \ge 2$，压入。栈 = [2, 3]。方案是 {2} | {3}，此刻确实合法（左边最大 2 不超过右边最小 3）。

$x = 1$：$1 < 3$，进入合并分支。弹出栈顶 3，$curMax = 3$，栈变为 [2]。检查栈顶 2 是否严格大于 1——是，弹出，$curMax = \max(3, 2) = 3$，栈变为空。循环因栈空退出，压回 3。栈 = [3]。方案变成一整块 {2, 3, 1}。这一步是全题最关键的一次操作：元素 1 比前面两个块的最大值都小，排序后必须跑到最前面，所以两刀都得撤销；而合并块的最大值取 3 而不是 1，保证了后续判断使用的是正确的前缀最大值。

$x = 4$：$4 \ge 3$，压入。栈 = [3, 4]。方案是 {2,3,1} | {4}。

$x = 4$：$4 \ge 4$，压入。栈 = [3, 4, 4]。方案是 {2,3,1} | {4} | {4}。这里就是 $\ge$ 的价值——两个相等的 4 可以各自成块。若条件写成 $>$，第二个 4 会走进合并分支，把两个 4 并成一块，答案变成 2。

返回栈大小 3。验证一下：三块分别排序得到 [1,2,3]、[4]、[4]，拼接为 [1,2,3,4,4]，正是全局排序结果，且再多切一刀都不行——{2,3,1} 内部任意切开都会让 1 停在错误的位置。

顺带看两个极端：arr = [5,4,3,2,1] 每个新元素都小于栈顶，每次都把栈清空后压回 5，最终栈只有一个元素，答案 1；arr = [7,7,7] 每个元素都满足 $x \ge$ 栈顶而入栈，答案 3。这两条正好卡住「合并逻辑」和「相等判定」两处最容易写错的地方。

代码实现

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> st = new ArrayDeque<>();
        for (int x : arr) {
            if (st.isEmpty() || x >= st.peekLast()) {
                st.addLast(x);
                continue;
            }

            int curMax = st.pollLast();
            while (!st.isEmpty() && st.peekLast() > x) {
                curMax = Math.max(curMax, st.pollLast());
            }
            st.addLast(curMax);
        }
        return st.size();
    }
}

func maxChunksToSorted(arr []int) int {
    st := make([]int, 0, len(arr))
    for _, x := range arr {
        if len(st) == 0 || x >= st[len(st)-1] {
            st = append(st, x)
            continue
        }

        curMax := st[len(st)-1]
        st = st[:len(st)-1]
        for len(st) > 0 && st[len(st)-1] > x {
            if st[len(st)-1] > curMax {
                curMax = st[len(st)-1]
            }
            st = st[:len(st)-1]
        }
        st = append(st, curMax)
    }
    return len(st)
}

复杂度分析

时间复杂度：$O(n)$。外层遍历每个元素一次；内层的合并循环看似嵌套，但每个元素最多入栈一次、出栈一次，所有合并操作的总次数不超过 $n$。这是均摊分析的标准结论，不能被内层 while 的表象误导成 $O(n^2)$。

空间复杂度：$O(n)$，栈在最坏情况（数组完全升序）下会存下全部 $n$ 个元素。相比「前缀最大值 + 后缀最小值」的写法，本解法只用一个栈而不是两个数组，且是在线的——每读入一个元素就能给出当前的块数。

关键点总结

「最多切几刀」等价于「逐个判定每刀是否合法」。切分点之间互不干扰，所以不需要搜索或 DP，把所有合法切分点全用上就是最优解。遇到「最多分成几段」的题，先确认段与段之间的决策是否独立，独立就退化成判定问题。

块的全部有效信息可以压缩成一个最大值。判定一刀能否切下只需要「左侧最大值」和「右侧最小值」，所以栈里存一个整数就够，不必记录块的边界或成员。识别出「哪些信息对后续决策有用」并只保留它们，是把复杂状态压成简单结构的通用方法。

在线修正优于离线预处理。前后缀极值的写法要先看完整个数组，而单调栈是「先乐观地切，遇到反例再合并」。这种「先假设最优、被打脸时回撤」的模式，在括号匹配、任务调度、区间合并里反复出现，是单调栈的思想内核。

等号的位置决定了重复元素的命运。入栈用 $\ge$、合并用严格 $>$，两处合起来才让「相等的元素可以各自成块」。凡是题目从「排列」放宽到「可重复」的变体（本题相对 769 题），第一件事就是逐个检查所有比较运算符的严格性。

合并后压回的是最大值而非当前元素。这一点关系到状态的语义完整性：栈顶必须始终代表「到目前为止的前缀最大值」，压错值会让后续所有判定基于一个偏小的基准。写单调栈时要时刻问自己「栈里存的到底是什么，它的语义在每次修改后还成立吗」。

面试视角：这题的标准回答路径是先给出判据 $\max(左) \le \min(右)$，再提出前后缀数组的 $O(n)$ 解法作为基线，最后给出单调栈解法并说明它是在线的、只用一个数组。面试官几乎一定会追问「和 769 题有什么区别」，答案是「769 的数组是排列，前缀最大值等于下标就能判定；本题有重复和任意值域，那个捷径失效」。另一个高频追问是「内层 while 会不会让复杂度变 $O(n^2)$」，要能用均摊论证回答：每个元素只入栈出栈各一次。能主动指出「入栈条件的 $\ge$ 和合并条件的 $>$ 不能互换」，说明你真的想过重复元素，是很强的加分信号。

易错点总结

错误写法：入栈条件写成 x > st.peek()（丢掉等号）。以 arr = [7, 7, 7] 为例，第二个 7 会走进合并分支，把两个 7 并成一块，第三个同理，最终返回 1，而正确答案是 3。全相同数组是这个 bug 最直接的照妖镜。

错误写法：合并循环条件写成 st.peek() >= x（多了等号）。以 arr = [2, 3, 2] 为例，处理末尾的 2 时栈是 [2, 3]：正确流程弹出 3 后发现栈顶 2 不严格大于 2 便停手，压回 3 得到栈 [2, 3]，答案 2（对应 {2} | {3,2}）；多了等号会把底部的 2 也并进来，栈变成 [3]，返回 1。相等时前块最大值恰为 $x$，切开是合法的。

错误写法：合并后压回 $x$ 而不是 $curMax$。以 arr = [2, 3, 1, 2] 为例，处理 1 时若压回 1，栈变成 [1]；接着 $x = 2 \ge 1$ 被压入，返回 2，而正确答案是 1——[2,3,1,2] 无论怎么切，第一块都必须包含全部元素才能让排序结果为 [1,2,2,3]。压回的必须是合并块的最大值。

错误写法：合并时只弹出一个栈顶就停止。以 arr = [2, 3, 1] 为例，弹出 3 后栈是 [2]，若不继续检查 2 是否大于 1，会直接压回 3 得到栈 [2, 3]，返回 2，而正确答案是 1。所有最大值大于 $x$ 的块都必须一并合并。

错误写法：沿用 769 题的「前缀最大值等于下标」判定。以 arr = [1, 1] 为例，前缀最大值是 1，下标 0 处 $1 \ne 0$ 判定失败，返回 1，而正确答案是 2。该判据只在数组是 $0$ 到 $n-1$ 的排列时成立。

错误写法：判据写成「前缀最大值 $\le$ 后缀最大值」或「前缀最小值 $\le$ 后缀最小值」。以 arr = [3, 1, 2] 为例，前缀最大 3 与后缀最大 2 比较会给出错误结论。正确判据必须是「左边的最大值 $\le$ 右边的最小值」，两侧取的极值方向相反。

错误写法：用 Stack 或数组但取错栈顶方向。Java 里用 ArrayDeque 时若混用 addLast 与 peekFirst，实际操作的是队列两端而非同一端，栈语义完全错乱。以 arr = [1, 2] 为例，peekFirst 拿到 1、addLast 追加 2，看似正确；但 arr = [2, 1] 时会把 1 与队首 2 比较后从队尾弹出，得到不可预期的结果。入栈出栈必须固定在同一端。

错误写法：把答案统计成「合并操作的次数」或「入栈次数」。以 arr = [2, 3, 1, 4, 4] 为例，入栈次数是 5（含合并后的压回），返回 5 而正确答案是 3。答案只能是遍历结束后栈的大小。

错误写法：合并时忘记更新 $curMax$，直接压回第一次弹出的栈顶之外的某个值。以 arr = [3, 5, 1] 为例，弹出 5 后再弹出 3，若压回的是最后弹出的 3 而非最大的 5，栈变成 [3]；后续若有元素 4 会因 $4 \ge 3$ 被切成新块，而它本应并入前块。虽然本例遍历已结束不暴露，但在更长的数组上会直接算错。

错误写法：以为内层 while 会导致超时而改成每次重新扫描整个栈求最大值。以 $n = 2000$ 的逆序数组为例，重新扫描会退化成 $O(n^2)$；而原写法因为每个元素只入栈出栈一次，总代价是 $O(n)$。误判复杂度反而写出更慢的代码，是常见的过度优化。

错误写法：Go 里弹栈写成 st = st[:len(st)-1] 之前先取值、之后又用旧的 len(st) 索引。以任意需要连续弹出两次的输入为例，第二次读取 st[len(st)-1] 时若长度变量没同步刷新，会读到已被逻辑弹出的元素或越界 panic。切片截断后长度立即变化，所有基于长度的索引都要重新计算。

相似题目

题目	难度	考察点
769. 最多能完成排序的块	中等	数组是 $0$ 到 $n-1$ 的排列，可用「前缀最大值等于下标」一行判定，无需栈
581. 最短无序连续子数组	中等	求的是必须重排的最短区间，同样靠前缀最大与后缀最小定位边界
739. 每日温度	中等	单调栈的入门形态，栈中存下标求下一个更大元素，弹栈时机与本题相反
84. 柱状图中最大的矩形	困难	单调递增栈，弹栈时结算以该柱为高的矩形，训练「弹栈瞬间做计算」的手感
42. 接雨水	困难	单调递减栈按层结算积水，也可用双指针，是前后缀极值思路的另一应用
496. 下一个更大元素 I	简单	单调栈配合哈希映射回答查询，重点在两个数组之间的下标转换
503. 下一个更大元素 II	中等	环形数组上的单调栈，需要遍历两轮或取模处理
56. 合并区间	中等	同样是「先分段再按需合并」，但合并依据是区间相交而非最大值比较