企业官网建设流程全解析

• 文档
• 教程
• 知识库

本文基于 InterviewGuide 仓库中《精选力扣 300+ 题目之数组》系列的 1089. 复写零 原题笔记展开。作为校招 / 社招高频的「数组就地修改」类题目，1089 考察的是在不借助额外数组的前提下，正确处理元素右移与越界截断的核心能力。读完本文，你将掌握该题的完整题意、两种典型的 C++ 实现（insert法 vs 栈辅助法）及各自的复杂度与性能差异，并理解从"能过"到"高效"的优化思路，可迁移到同类双指针 / 栈模拟题中。

题目回顾与核心考点

原题描述

给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍（即每个 0 变成两个 0），并将其余的元素向右平移。

• 注意：请不要在超过该数组长度的位置写入元素，即结果数组长度与原数组保持一致，多出来的元素被丢弃。
• 要求：请对输入的数组就地进行上述修改，不要从函数返回任何东西（函数签名在 C++ 中为void duplicateZeros(vector<int>& arr)）。

示例与边界

示例 1

输入：[1,0,2,3,0,4,5,0] 输出：null 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

逐位推演：索引 1 处的0复写为两个 0，占用 1、2 两个位置；索引 4 处的0复写为两个 0，占用 4、5 两个位置；末尾的0因数组长度固定（8），只能写入一个 0（即 7 号位的0保留），后面的5、0被挤出数组。

示例 2

输入：[1,2,3] 输出：null 解释：调用函数后，输入的数组将被修改为：[1,2,3]

数组不含 0，则结果与原数组完全一致。

提示（数据范围）

1 <= arr.length <= 10000 0 <= arr[i] <= 9

数组长度上限 10000，元素取值仅为 0~9 的单数字，意味着 0 出现频率可能很高（极端情况下全为 0），这对解法的时间复杂度提出了要求——纯暴力逐个搬移在极端输入下会退化到 O(n²) 而超时，这也是原文档把两版解法称为"比较耗时"与"减少时间"的原因。

解法一：insert+pop_back直接复写（直观但偏慢）

原文档给出的第一版实现，是"所见即所得"的直观思路：遇到 0 就原地插入一个 0，再把数组尾部的元素弹出，以维持数组长度不变。

void duplicateZeros(vector<int>& arr) { for (int i = 0; i < arr.size(); i++) { if (arr[i] == 0) { arr.insert(arr.begin() + i, 0); // 在 i 位置复写一个 0 arr.pop_back(); // 这步很关键：弹出末尾元素，保持数组长度固定 i++; // 跳过新插入的 0，避免重复处理 } } }

关键细节拆解

1. arr.insert(arr.begin() + i, 0)：在索引i处插入一个 0，原i位置及其之后的所有元素整体右移一位。此时数组长度变为size + 1。
2. arr.pop_back()（原文档特意标注"这步很关键"）：vector::insert会扩容数组，若不立即弹出末尾元素，数组长度就会超过题目"长度固定"的约束，同时下一个0的插入位置也会错乱。弹出末尾元素既维持了长度不变，也天然实现了"不要超过数组长度的位置写入元素"的截断语义——被挤出的元素正是原数组末尾的元素。
3. i++：插入完成后，arr[i]位置已是新插入的 0，若不自增，下一轮循环会再次命中这个 0 造成无限复写；自增后跳过新 0，继续检查原始数组的下一个元素。

复杂度与性能实测

• 时间复杂度：最坏情况下（大量 0）insert单次为 O(n)，整体退化为O(n²)。
• 空间复杂度：O(1)，仅使用了常数级额外空间（不计算insert内部移动的临时开销）。

原文档记录了在力扣平台上的实测表现：

执行用时 :48 ms, 在所有 C++ 提交中击败了56.70%的用户 内存消耗 :9.5 MB, 在所有 C++ 提交中击败了100.00%的用户

可见内存表现极佳（击败 100% 用户），但耗时已属中游水平。在 10000 长度的极端输入下存在超时风险，因此原文档紧接着给出了优化版本。

解法二：借助栈预处理，将时间降为 O(n)

第二版的核心思路是先用栈把"结果数组"完整模拟出来，但只模拟到长度达到arr.size()为止（超出部分不再入栈），最后再把栈内容回填进原数组。这样避免了insert带来的 O(n) 元素搬移。

void duplicateZeros(vector<int>& arr) { stack<int> st; int temp = 0; // temp 记录当前已模拟的长度 for (int i = 0; i < arr.size(); ++i) { st.push(arr[i]); ++temp; if (arr[i] == 0) { // 遇到 0，额外复写一个 0 if (temp == arr.size()) break; // 长度已满，复写的 0 不再入栈 ++temp; st.push(0); } if (temp == arr.size()) break; // 模拟长度已满，提前终止 } arr.clear(); // 清空原数组 while (!st.empty()) { arr.push_back(st.top()); // 栈顶是最新元素，先取栈顶 st.pop(); } reverse(arr.begin(), arr.end()); // 栈是后进先出，需反转恢复顺序 }

执行流程推演（以 [1,0,2,3,0,4,5,0] 为例）

• 依次入栈1（temp=1）、0（temp=2），遇到 0 再入栈一个0（temp=3）……继续入栈2（temp=4）、3（temp=5）、0（temp=6），再入栈一个0（temp=7），继续入栈4（temp=8，等于 arr.size()，break）。
• 此时栈内自底向上依次为1,0,0,2,3,0,0,4，恰好是最终答案。
• 清空原数组后，从栈顶依次弹出回填：4,0,0,3,2,0,0,1，最后reverse得到1,0,0,2,3,0,0,4。

两个 break 的作用

• 第一个break：当temp == arr.size()时，说明模拟长度已满，本次遇到的 0 已经无法再容纳一个额外的复写 0（对应题目"不要在超过数组长度的位置写入元素"），直接终止循环。
• 第二个break：普通元素入栈后若长度已满，同样立即终止，避免无谓的后续扫描。

这一版本质上是用 O(n) 的栈空间换取 O(n) 的时间——只扫描一遍数组，每个元素最多入栈一次，整体时间复杂度严格 O(n)。

复杂度与性能实测

执行用时 :28 ms, 在所有 C++ 提交中击败了90.69%的用户 内存消耗 :9.5 MB, 在所有 C++ 提交中击败了100.00%的用户

相比第一版，耗时从 48ms 降到 28ms，击败比例从 56.70% 提升到 90.69%，说明预处理思路在时间维度上优势明显；而内存仍为 9.5MB、击败 100% 用户，在本题数据规模（长度 ≤ 10000）下栈的额外开销可忽略。

两种解法对比与优化思路延伸

核心权衡：题目要求就地修改且长度固定，解法一利用vector的insert/pop_back以"自损"的方式实现了最直观的语义，代码最简短，但最坏情况 O(n²)；解法二把"搬移"换成"模拟 + 回填"，用一次线性扫描解决问题，是典型的时间换空间的取舍——在arr[i]取值范围仅 0~9、0 可能高频出现的数据特征下，O(n) 显然更稳妥。

可迁移的进阶思路：本题更优的常规做法是两次扫描 + 双指针——第一次从右往左统计需要复写 0 的数量以确定最终长度，第二次从右往左原地写入，可将空间复杂度也压到 O(1)。解法二栈模拟中"先确定有效长度、再回填"的思想，正是这一思路的雏形。

实战验证与仓库上下文

本解法笔记来自阿秀 InterviewGuide 项目《精选力扣 300+ 题目》的数组分类下的 Easy 档位。该项目将算法模块按照 基础算法、剑指 Offer 67 题 与力扣精选题目分层组织，适用于校招、社招工作党以及打算转行计算机的非科班人士。

读者可以直接在本地用任意 C++ 编译器（如 g++）验证本题解法：

# 以解法一为例，将函数体放入 main 后编译运行 g++ -std=c++11 -O2 main.cpp -o main && ./main

验证要点建议覆盖三类用例：

1. 含多个 0 的常规用例：[1,0,2,3,0,4,5,0]→ 期望[1,0,0,2,3,0,0,4]；
2. 无 0 用例：[1,2,3]→ 期望[1,2,3]（验证不破坏原数组）；
3. 末尾为 0 的截断用例：[0,0]→ 期望[0,0]（两个 0 复写后长度仍为 2，验证pop_back/break的截断逻辑）。

小结

LeetCode 1089「复写零」是一道将"数组元素右移""就地修改""长度截断"三个考察点合一的经典 Easy 题。原文档给出的两版 C++ 解法恰好构成了一个完整的优化链条：解法一以insert+pop_back直白实现语义，胜在思路清晰；解法二借助栈先模拟后回填，将最坏 O(n²) 优化为 O(n)，实测耗时从 48ms 降至 28ms。理解这两版代码背后的"长度固定"约束与"截断"处理，你便掌握了处理此类就地数组题的核心套路，也能为后续更进阶的双指针原地写法打下基础。

• 文档
• 教程
• 知识库