1089 复写零：为什么必须从后往前写？cur/dest 双指针把“扩容数组”模拟出来

这题的表面操作很简单：数组里每出现一个 0，就复制一份 0，其他元素整体右移。但题目有一个很阴险的限制：

数组长度固定，不能在超过数组长度的位置写入元素，必须原地修改。

这意味着不能真的开一个新数组随便写（当然可以，但题目希望原地），也不能从左往右直接挪（很容易把还没处理的元素覆盖掉）。

所以核心问题变成：

如何在不丢数据的前提下，把元素“右移并复写 0”，且只写进数组长度范围内？

答案就是：从后往前写。

---

1. 为什么从后往前写？

假设从前往后改：

• 遇到 0，要把后面元素都往右挪
• 但你一挪，后面元素的位置就变了，下一步读取就乱
• 更致命的是：很可能把“还没读取的原始值”覆盖掉

而从后往前写的好处是：

• 右移本质上是“往右填”
• 从右往左填时，写入的位置永远在“未读取区域”的右侧
• 读的位置在左，写的位置在右，不会覆盖未来还要读的数据

所以这题的正确姿势就是：先确定最终每个元素应该落到哪里，再从后往前回填。

---

2. 两个指针：cur 和 dest，分别代表什么？

来看这段关键设计：

• cur：指向原数组当前扫描的位置（从左到右走）
• dest：指向“如果数组可以无限长，复写 0 后的数组下标会走到哪里”

dest 的意义很重要，它是在模拟“扩容后的下标”。

规则是：

• 遇到非 0：dest += 1
• 遇到 0：dest += 2（因为要写两个 0）

当 dest 走到 n-1 或超过 n-1 时，说明扩容后的效果已经覆盖到了原数组最后一格，回填就可以开始了。

---

3. 第一步：找到最后一个参与回填的原始元素

来看这段代码（能 AC 的版本）：

int cur = 0;
int dest = -1;
int n = arr.length;

while (cur < n) {
    if (arr[cur] == 0) {
        dest += 2;
    } else {
        dest += 1;
    }
    if (dest >= n - 1) break;
    cur++;
}

这里做的事是：

• 从左到右扫 arr[cur]
• 用 dest 计算“复写后会走到的位置”
• 一旦 dest 覆盖到数组最后一格（>= n-1），就停

为什么停得这么精确？
因为后面要从 cur 开始往前回填，如果 cur 多走一步或者少走一步，回填起点就会错，整个数组就会乱。

---

4. 第二步：边界处理 —— 为什么会出现 dest == n？

这一步经常让人迷惑：

if (dest == n) {
    arr[n - 1] = 0;
    cur--;
    dest -= 2;
}

理解它要抓住一点：dest 是“扩容数组下标”。

当 dest == n 时，意味着：

• 最后一次遇到的是 0
• 在扩容数组里，它应该占用两个格子
• 但真实数组只剩下最后一格能写（下标 n-1）
• 所以只能写进一个 0，另一个 0 会越界丢弃

于是必须先把 arr[n-1] 写成 0，然后：

• cur--：这个 0 的“第二个副本”没法写了，相当于消耗掉一次位置
• dest -= 2：把 dest 拉回到合法回填区间

这一步不做，后面的回填会出现越界或写错位置。

---

5. 第三步：从后往前回填（关键：读 cur，写 dest）

回填代码：

while (cur >= 0) {
    if (arr[cur] != 0) {
        arr[dest--] = arr[cur--];
    } else {
        arr[dest--] = 0;
        arr[dest--] = 0;
        cur--;
    }
}

逻辑是：

• 如果 arr[cur] 不是 0：只写一次
• 如果是 0：写两次 0（复写）
• 每写一次 dest--，每处理一个原元素 cur--

为什么不会覆盖？
因为 dest 永远在右侧，cur 永远在左侧，而且 dest 是从末尾向前走，写的位置不会影响还没读取的 arr[cur]（因为 cur 更靠左）。

---

6. 为什么用 for 循环版本会失败？

很多人把“找最后一个元素”的 while 换成 for，例如：

for (; dest < n; cur++) {
    if (arr[cur] == 0) dest += 2;
    else dest++;
}

这会炸的原因很直接：

• 循环条件只看 dest < n，但 没有保证 cur < n
• 在没有 0 的数组里，dest 增长慢，cur 会一路加到 n，然后访问 arr[cur] 越界

另外它的停止条件也不精确：应该在 dest >= n-1 立刻停，否则 cur 会多走一步，回填起点错位。

这就是 why：while 版本停得精确且安全，for 版本边界条件写错就容易越界或错位。

---

完整可用代码（Java，原地修改，AC）

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int cur = 0;
        int dest = -1;

        // 1) 找到最后一个需要参与“复写/右移”的原数组下标 cur
        while (cur < n) {
            if (arr[cur] == 0) {
                dest += 2;
            } else {
                dest += 1;
            }
            if (dest >= n - 1) break;
            cur++;
        }

        // 2) 边界处理：dest == n 说明最后一个 0 只能写进一个
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }

        // 3) 从后往前回填
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
}

---

最后总结：这题真正要掌握的“套路”

• 原地右移类题目，优先考虑从后往前写
• 用 dest 模拟“扩容后的下标”，把最终位置算出来
• 处理 dest == n 的边界（最后一个 0 只有一格能写）
• 回填阶段：读 cur，写 dest，一步一步往前推

把这套逻辑吃透后，很多“数组原地移动/压缩/扩展”题都会变得很像同一种题。（双指针问题专门用来解决数组移动/区间划分问题）