最多能完成排序的块

为什么?排好序后下标 i 上应该是数字 i。如果前 i+1 个数的最大值恰好是 i,说明 0..i 这些数字正好填满了 0..i 这些位置,左边自成一块、和右边再不纠缠,所以能切。

准备 · arr = [1,0,2,3,4]：我们让一个指针从左往右扫,一路维护「到目前为止见过的最大值」maxv。每到一格,先更新 maxv,再看 maxv 是否等于当前下标。

i=0 · 更新 maxv：指针落在下标 0,值是 1。更新前缀最大值:maxv = 1。

i=0 · maxv=1 ≠ 0 · 不能切：maxv(1) ≠ i(0)。出现了比 0 大的数,说明数字 0 还在后面没遇到,这一块没法封口,不能切。

i=1 · 更新 maxv：指针挪到下标 1,值是 0。maxv 取较大者还是 1(没变大)。

i=1 · maxv=1 == 1 · 切!：maxv(1) == i(1)!前两格里的数 {0,1} 正好填满位置 {0,1},左边 [1,0] 自成一块。切一刀,块数 = 1。

i=2 · 更新 maxv：指针到下标 2,值是 2。maxv 被刷新成 2。

i=2 · maxv=2 == 2 · 切!：maxv(2) == i(2)!到这里 0..2 的数正好填满 0..2 的位置,[2] 单独成块。块数 = 2。

i=3 · 更新 maxv：指针到下标 3,值是 3。maxv 刷新成 3。

i=3 · maxv=3 == 3 · 切!：maxv(3) == i(3)![3] 又是独立一块。块数 = 3。

i=4 · 更新 maxv：指针到最后一格下标 4,值是 4。maxv 刷新成 4。

i=4 · maxv=4 == 4 · 切!完成：maxv(4) == i(4)!最后一刀,[4] 独立成块。扫完一遍,总共切出 4 块,这就是答案。

结果 · 4 块：每个「maxv == i」的位置都是一个切口。整趟一次遍历、一个变量,O(n) 就数完了块数。

下面用倒序数组走一遍,体会「前面只要冒出一个大数,后面就被它牢牢绑住切不开」。

反例 · arr = [4,3,2,1,0]：换成完全倒序的 [4,3,2,1,0],规则不变,看 maxv 怎么一路被 4 卡住。

i=0 · 更新 maxv：指针落在下标 0,第一格就是最大值 4,maxv 直接被顶到 4。

i=0 · maxv=4 ≠ 0 · 不切：maxv(4) ≠ i(0)。这个 4 要等到下标 4 才安顿好,在那之前哪也切不了。

i=1 · maxv=4 ≠ 1：下标 1,值 3,比 4 小,maxv 不变,仍是 4。4 ≠ 1,切不开。

i=2 · maxv=4 ≠ 2：下标 2,值 2,maxv 还是 4。4 ≠ 2,继续不能切。

i=3 · maxv=4 ≠ 3：下标 3,值 1,maxv 仍 4。4 ≠ 3,还差一步。

i=4 · maxv=4 == 4 · 只切这一刀：直到最后一格 i=4,maxv 才等于下标。整个数组只能算 1 块——前面的大数把后面全锁死了,这正是贪心判据的威力。

雷区实演 · 看相邻会切错：假如只盯相邻两格的大小关系,就解释不清「为什么 i=0 不能切、i=1 能切」。真正的依据是前缀最大值 maxv 何时追上下标,这是全局信息,相邻比较替代不了。

边界三连：想清楚「全升序切满 n 块」「全倒序只切 1 块」「最小乱序切 1 块」三种极端,代码就稳了。

面试追问：把「贪心为何对」和「推广到 LC768」讲清楚,是这题面试的高分点。