前言

LeetCode 第 769 题「最多能完成排序的块」给一个长度为 n 的数组，它是0到n-1的一个排列。要求把数组切成尽量多的连续块，对每块单独排序后，按原顺序拼接起来，结果等于整个数组升序排列。

题目的关键约束是「排列」：每个值恰好出现一次，取值范围正好是0..n-1。这个约束让问题有一个非常简洁的 O(n) 解法——维护前缀最大值，当最大值等于当前下标时，就可以在这里切一刀。

初学者容易把它做成「对每个前缀排序再比较」，复杂度 O(n² log n)，虽然能过小数据，但完全没抓住排列的性质。另一个误区是把 769 的贪心直接套到 768（允许重复值）上，那里前缀最大值等于下标的条件不再成立。

本文讲贪心的正确性、边界条件，以及一个适用于重复值版本的单调栈解法，最后列出常见坑点。

一、问题转化

把一个块切在位置i之后（即前i+1个元素为一块），需要满足什么条件？

由于整个数组是0..n-1的排列，前i+1个位置最终应该放的就是0..i这i+1个数。如果前i+1个元素恰好就是集合{0, 1, ..., i}，那么它们单独排序后正好占据排序结果的前i+1个位置，这一刀就是合法的。

而「前i+1个元素恰好是0..i」等价于：前i+1个元素的最大值等于i。

理由：

• 
  
• 如果最大值等于i，由于所有元素互不相同且都非负，这i+1个元素必然是0..i的某个排列。
• 
  
• 如果最大值大于i，说明有一个本该放在后面的数跑到了前面，这一刀切下去，前一块排序后无法与后一块衔接。
• 
  

所以算法就是：从左到右扫描，维护当前前缀最大值curMax，每当curMax == i时，块数加一。

二、贪心实现

// 适用于 C++17
#include <algorithm>
#include <vector>

int maxChunksToSorted(const std::vector<int>& arr) {
int chunks = 0;
int curMax = -1;
for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
curMax = std::max(curMax, arr[i]);
if (curMax == i) {
++chunks;
}
}
return chunks;
}

几个细节：

• 
  
• curMax初始化为-1，保证第一个元素（最小为 0）一定能更新它。如果初始化成 0，遇到arr[0] == 0时也正确，但如果以后把函数改成处理其他范围，-1更稳妥。
• 
  
• 循环变量用int，避免size_t与int比较时的符号警告。arr.size()先转成int，前提是长度不超过INT_MAX，这在题目约束内成立。
• 
  
• 条件必须是curMax == i，不能写成>=。虽然在排列的前提下curMax >= i恒成立（前缀最大值至少是i），但==才表达「恰好填满」的语义。如果输入不满足排列约束，>=会给出错误答案。
• 
  
• 空数组时循环不执行，返回 0，符合「没有块」的语义。
• 
  

复杂度：时间 O(n)，空间 O(1)。

2.1 为什么贪心是最优的

设第一个合法切点在i。任何方案的第一块都必须至少包含前i+1个元素，否则这块的最大值会大于它的结束下标，排序后无法归位。因此第一块不可能更短，切在i不会比任何其他方案差。切完之后，问题在剩余部分上独立，归纳可得贪心取到最大块数。

这个论证依赖「排列」这一前提。若数组有重复值，前缀最大值等于下标不再等价于「前缀恰好是某个值域集合」，贪心失效。

三、含重复值的版本

LeetCode 768 允许数组中有重复元素，要求同样切块后各自排序、拼接后整体非递减。此时 769 的贪心不再适用。

一个通用解法是单调栈：

// 适用于 C++17
#include <algorithm>
#include <stack>
#include <vector>

int maxChunksToSortedII(const std::vector<int>& arr) {
std::stack<int> st;
for (int x : arr) {
if (st.empty() || x >= st.top()) {
st.push(x);
} else {
int top = st.top();
while (!st.empty() && st.top() > x) {
st.pop();
}
st.push(top);
}
}
return static_cast<int>(st.size());
}

思路是：栈中每个元素代表一个「当前块的 Maximum」。遇到比栈顶大的值，它可以独立成块，直接入栈；遇到比栈顶小的值，说明它必须和前面的若干块合并，于是把那些最大值大于它的块全部弹出，最后把原来的最大块值压回去，表示合并后的块。

对 769 的输入，这个算法同样给出正确答案，只是多用了 O(n) 的栈空间。面试时如果先给出 769 的 O(1) 贪心，再补充这个通用版本，能体现对问题约束的理解。

完整示例

// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <vector>

int maxChunksToSorted(const std::vector<int>& arr) {
int chunks = 0;
int curMax = -1;
for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
curMax = std::max(curMax, arr[i]);
if (curMax == i) {
++chunks;
}
}
return chunks;
}

int main() {
const std::vector<std::vector<int>> cases{
{4, 3, 2, 1, 0},
{1, 0, 2, 3},
{0, 1, 2, 3},
{2, 0, 1}
};

for (const auto& arr : cases) {
std::cout << maxChunksToSorted(arr) << '\n';
}
return 0;
}

按标准语义，四个用例的结果分别是 1、3、4、1。逐个代入验证：

• 
  
• {4,3,2,1,0}：i=0到i=3时前缀最大值都是 4，不等于下标；只有i=4时curMax == 4，块数加一，最终为 1。只能整体成块。
• 
  
• {1,0,2,3}：i=0时curMax=1，不等于 0；i=1时curMax=1，等于 1，记一块；i=2时curMax=2，再记一块；i=3时curMax=3，再记一块，共 3 块。
• 
  
• {0,1,2,3}：每个位置都满足curMax == i，共 4 块。
• 
  
• {2,0,1}：i=0时curMax=2；i=1时仍是 2；i=2时curMax=2，等于下标，记一块，最终为 1。
• 
  

这段推演说明：贪心条件看起来简单，仍然要拿具体数组逐项代入。尤其是最后一个用例，凭直觉容易把「3 个元素」直接当成「3 块」，而实际上前两个位置的最大值都超过了各自的下标，必须合并成一个整体。

常见坑点

1. 
   
2. ❌ 对每个前缀排序后与0..i比较：
3. 
   

``cpp for (int i = 0; i < n; ++i) { std::vector<int> tmp(arr.begin(), arr.begin() + i + 1); std::sort(tmp.begin(), tmp.end()); // 再逐个比较 }`` ✅ 用前缀最大值，O(n) 完成。

1. 
   
2. ❌ 把条件写成curMax >= i：
3. 
   

``cpp if (curMax >= i) ++chunks; // 排列下恒成立，块数等于 n`✅ 必须是curMax == i`。

1. 
   
2. ❌curMax初始化为 0，遇到全负或非排列输入出错。
3. 
   

✅ 用-1或arr[0]作为初值，并在循环内统一更新。

1. 
   
2. ❌ 把 769 的贪心用于含重复值的数组：
3. 
   

``cpp // arr = {1, 1, 0}，前缀最大值条件失效`` ✅ 改用单调栈或排序后比较前缀。

1. 
   
2. ❌ 循环里int i与arr.size()直接比较，触发符号警告。
3. 
   

✅ 先把长度转成int，或用std::size_t并配套转换。

1. 
   
2. ❌ 忘记空数组：
3. 
   

``cpp int curMax = arr[0]; // 空数组越界`✅ 用-1` 初始化并让循环自然处理空输入。

1. 
   
2. ❌ 认为「块内元素必须连续」。
3. 
   

✅ 块内元素不要求连续，只要求排序后能拼成整体有序；{1,0}是一块，元素并不连续。

总结

这道题的价值在于展示「约束如何简化算法」：一旦知道数组是排列，判断一块是否合法只需要一个前缀最大值。离开这个约束，同样的贪心立刻失效，必须换用单调栈。读题时先确认约束，再选方法，比记住某个模板更重要。