LeetCode 769中等贪心
最多能完成排序的块 图解题解
这道题到底在问什么
给一个长度为 n 的数组 arr,它是 0 到 n−1 的一个排列。把它切成若干连续的块,每块单独排序后拼起来,要让整体变成升序。问最多能切成多少块。
- arr
- [1,0,2,3,4]
- 输出
- 4
- 切法
- [1,0] | [2] | [3] | [4]
最优解：一步一步想明白
- 3为什么?排好序后下标 i 上应该是数字 i。如果前 i+1 个数的最大值恰好是 i,说明 0..i 这些数字正好填满了 0..i 这些位置,左边自成一块、和右边再不纠缠,所以能切。
- 4维护前缀最大值 maxv我们让一个指针从左往右扫,一路维护「到目前为止见过的最大值」maxv。每到一格,先更新 maxv,再看 maxv 是否等于当前下标。
- 5maxv = max(0, 1) = 1指针落在下标 0,值是 1。更新前缀最大值:maxv = 1。
- 61 > 0,左边还欠着 0maxv(1) ≠ i(0)。出现了比 0 大的数,说明数字 0 还在后面没遇到,这一块没法封口,不能切。
- 7maxv = max(1, 0) = 1指针挪到下标 1,值是 0。maxv 取较大者还是 1(没变大)。
- 8切出第 1 块 [1,0]maxv(1) == i(1)!前两格里的数 {0,1} 正好填满位置 {0,1},左边 [1,0] 自成一块。切一刀,块数 = 1。
- 9maxv = max(1, 2) = 2指针到下标 2,值是 2。maxv 被刷新成 2。
- 10切出第 2 块 [2]maxv(2) == i(2)!到这里 0..2 的数正好填满 0..2 的位置,[2] 单独成块。块数 = 2。
- 11maxv = max(2, 3) = 3指针到下标 3,值是 3。maxv 刷新成 3。
- 12切出第 3 块 [3]maxv(3) == i(3)![3] 又是独立一块。块数 = 3。
- 13maxv = max(3, 4) = 4指针到最后一格下标 4,值是 4。maxv 刷新成 4。
- 14切出第 4 块 [4]maxv(4) == i(4)!最后一刀,[4] 独立成块。扫完一遍,总共切出 4 块,这就是答案。
- 15[1,0] | [2] | [3] | [4]每个「maxv == i」的位置都是一个切口。整趟一次遍历、一个变量,O(n) 就数完了块数。
- 16下面用倒序数组走一遍,体会「前面只要冒出一个大数,后面就被它牢牢绑住切不开」。
- 17maxv = 0,块数 = 0换成完全倒序的 [4,3,2,1,0],规则不变,看 maxv 怎么一路被 4 卡住。
- 18maxv = max(0, 4) = 4指针落在下标 0,第一格就是最大值 4,maxv 直接被顶到 4。
- 19开头就来个最大值 4maxv(4) ≠ i(0)。这个 4 要等到下标 4 才安顿好,在那之前哪也切不了。
- 20maxv 还卡在 4下标 1,值 3,比 4 小,maxv 不变,仍是 4。4 ≠ 1,切不开。
- 21依旧被 4 压着下标 2,值 2,maxv 还是 4。4 ≠ 2,继续不能切。
- 22马上到头了下标 3,值 1,maxv 仍 4。4 ≠ 3,还差一步。
- 23到末尾才追平,1 块直到最后一格 i=4,maxv 才等于下标。整个数组只能算 1 块——前面的大数把后面全锁死了,这正是贪心判据的威力。
- 27[1,0,2] 误判假如只盯相邻两格的大小关系,就解释不清「为什么 i=0 不能切、i=1 能切」。真正的依据是前缀最大值 maxv 何时追上下标,这是全局信息,相邻比较替代不了。
⚠️ 容易写错的地方
✗ 错：用「最小值」或单纯比较相邻元素判切点
✓ 对：维护「前缀最大值」与下标 i 比较
能否封块取决于左边最大值是否已落位(== i),不是局部相邻关系
✗ 错：max_so_far 初值设成 arr[0] 或 -1 后下标错位
✓ 对：因排列含 0,maxv 初值设 0、循环内先更新再比较 i
下标从 0 起,maxv 初值与比较时机错一位就会多切或少切
完整代码（Python / C++ / Java）
Python
class Solution:
def maxChunksToSorted(self, arr):
max_so_far = 0
chunks = 0
for i in range(len(arr)):
if arr[i] > max_so_far:
max_so_far = arr[i]
if max_so_far == i: # 前缀最大值追平下标 → 切
chunks += 1
return chunksC++
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int maxSoFar = 0, chunks = 0;
for (int i = 0; i < (int)arr.size(); i++) {
maxSoFar = max(maxSoFar, arr[i]);
if (maxSoFar == i) chunks++; // 追平就切
}
return chunks;
}
};Java
class Solution {
public int maxChunksToSorted(int[] arr) {
int maxSoFar = 0, chunks = 0;
for (int i = 0; i < arr.length; i++) {
maxSoFar = Math.max(maxSoFar, arr[i]);
if (maxSoFar == i) chunks++; // 追平就切
}
return chunks;
}
}复杂度
时间复杂度
O(n)
只从左到右扫一遍数组,每格做一次取最大值和一次相等判断,共 n 次 → O(n)
空间复杂度
O(1)
只用了 max_so_far 和 chunks 两个变量,不随数组规模增长 → O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最多能完成排序的块 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么贪心(前缀最大值==下标)一定对?+
因为是 0~n−1 的排列,排序后第 i 位是 i。前缀最大值等于 i 时,0..i 的数恰好占满 0..i 的位置,左段闭合可独立排序,切口必然合法。
如果数组不是排列,而是任意可重复整数(LC768)怎么办?+
比下标不再奏效,改为比较『前缀最大值』和『后缀最小值』:在 i 处能切当且仅当 前缀max(0..i) ≤ 后缀min(i+1..n−1),需预处理后缀最小值数组,仍 O(n)。
为什么是 O(n) 而不能更快?+
至少要看每个元素一次才能确定切点,O(n) 已是下界。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最多能完成排序的块 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。