C++实现LeetCode(769.可排序的最大块数)

前言LeetCode 第 769 题「最多能完成排序的块」给一个长度为 n 的数组它是0到n-1的一个排列。要求把数组切成尽量多的连续块对每块单独排序后按原顺序拼接起来结果等于整个数组升序排列。题目的关键约束是「排列」每个值恰好出现一次取值范围正好是0..n-1。这个约束让问题有一个非常简洁的 O(n) 解法——维护前缀最大值当最大值等于当前下标时就可以在这里切一刀。初学者容易把它做成「对每个前缀排序再比较」复杂度 O(n² log n)虽然能过小数据但完全没抓住排列的性质。另一个误区是把 769 的贪心直接套到 768允许重复值上那里前缀最大值等于下标的条件不再成立。本文讲贪心的正确性、边界条件以及一个适用于重复值版本的单调栈解法最后列出常见坑点。一、问题转化把一个块切在位置i之后即前i1个元素为一块需要满足什么条件由于整个数组是0..n-1的排列前i1个位置最终应该放的就是0..i这i1个数。如果前i1个元素恰好就是集合{0, 1, ..., i}那么它们单独排序后正好占据排序结果的前i1个位置这一刀就是合法的。而「前i1个元素恰好是0..i」等价于前i1个元素的最大值等于i。理由如果最大值等于i由于所有元素互不相同且都非负这i1个元素必然是0..i的某个排列。如果最大值大于i说明有一个本该放在后面的数跑到了前面这一刀切下去前一块排序后无法与后一块衔接。所以算法就是从左到右扫描维护当前前缀最大值curMax每当curMax i时块数加一。二、贪心实现// 适用于 C17#include algorithm#include vectorint maxChunksToSorted(const std::vectorint arr) {int chunks 0;int curMax -1;for (int i 0; i static_castint(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。任何方案的第一块都必须至少包含前i1个元素否则这块的最大值会大于它的结束下标排序后无法归位。因此第一块不可能更短切在i不会比任何其他方案差。切完之后问题在剩余部分上独立归纳可得贪心取到最大块数。这个论证依赖「排列」这一前提。若数组有重复值前缀最大值等于下标不再等价于「前缀恰好是某个值域集合」贪心失效。三、含重复值的版本LeetCode 768 允许数组中有重复元素要求同样切块后各自排序、拼接后整体非递减。此时 769 的贪心不再适用。一个通用解法是单调栈// 适用于 C17#include algorithm#include stack#include vectorint maxChunksToSortedII(const std::vectorint arr) {std::stackint 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_castint(st.size());}思路是栈中每个元素代表一个「当前块的 Maximum」。遇到比栈顶大的值它可以独立成块直接入栈遇到比栈顶小的值说明它必须和前面的若干块合并于是把那些最大值大于它的块全部弹出最后把原来的最大块值压回去表示合并后的块。对 769 的输入这个算法同样给出正确答案只是多用了 O(n) 的栈空间。面试时如果先给出 769 的 O(1) 贪心再补充这个通用版本能体现对问题约束的理解。版本约束时间空间方法7690..n-1的排列O(n)O(1)前缀最大值768允许重复O(n)O(n)单调栈通用任意整数O(n log n)O(n)排序后比较前缀完整示例// 适用于 C17#include algorithm#include iostream#include vectorint maxChunksToSorted(const std::vectorint arr) {int chunks 0;int curMax -1;for (int i 0; i static_castint(arr.size()); i) {curMax std::max(curMax, arr[i]);if (curMax i) {chunks;}}return chunks;}int main() {const std::vectorstd::vectorint 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}i0到i3时前缀最大值都是 4不等于下标只有i4时curMax 4块数加一最终为 1。只能整体成块。{1,0,2,3}i0时curMax1不等于 0i1时curMax1等于 1记一块i2时curMax2再记一块i3时curMax3再记一块共 3 块。{0,1,2,3}每个位置都满足curMax i共 4 块。{2,0,1}i0时curMax2i1时仍是 2i2时curMax2等于下标记一块最终为 1。这段推演说明贪心条件看起来简单仍然要拿具体数组逐项代入。尤其是最后一个用例凭直觉容易把「3 个元素」直接当成「3 块」而实际上前两个位置的最大值都超过了各自的下标必须合并成一个整体。常见坑点❌ 对每个前缀排序后与0..i比较cpp for (int i 0; i n; i) { std::vectorint tmp(arr.begin(), arr.begin() i 1); std::sort(tmp.begin(), tmp.end()); // 再逐个比较 } ✅ 用前缀最大值O(n) 完成。❌ 把条件写成curMax icpp if (curMax i) chunks; // 排列下恒成立块数等于 n✅ 必须是curMax i。❌curMax初始化为 0遇到全负或非排列输入出错。✅ 用-1或arr[0]作为初值并在循环内统一更新。❌ 把 769 的贪心用于含重复值的数组cpp // arr {1, 1, 0}前缀最大值条件失效 ✅ 改用单调栈或排序后比较前缀。❌ 循环里int i与arr.size()直接比较触发符号警告。✅ 先把长度转成int或用std::size_t并配套转换。❌ 忘记空数组cpp int curMax arr[0]; // 空数组越界✅ 用-1 初始化并让循环自然处理空输入。❌ 认为「块内元素必须连续」。✅ 块内元素不要求连续只要求排序后能拼成整体有序{1,0}是一块元素并不连续。总结要点结论核心条件前缀最大值等于当前下标时间复杂度O(n)空间复杂度O(1)前提数组是0..n-1的排列重复值版本单调栈O(n) 空间这道题的价值在于展示「约束如何简化算法」一旦知道数组是排列判断一块是否合法只需要一个前缀最大值。离开这个约束同样的贪心立刻失效必须换用单调栈。读题时先确认约束再选方法比记住某个模板更重要。