【力扣】复写零，栈 + 双指针法

复写零原题地址

方法一：双指针法

从前向后复写，会造成覆盖。所以，应该从后向前复写，这样我们可以考虑维护一个栈。遍历数组，如果遇到非零元素，就入栈一次；如果遇到零，就入栈两次。当栈中的元素个数超出数组的元素个数时，把栈中的元素重新从后向前写入数组即可。

如：对于数组 [1 2 0 0 3 0 4] ，

1 ：入栈 1 次： [1]

2 ：入栈 1 次： [1 2]

0 ：入栈 2 次： [1 2 0 0]

0 ：入栈 2 次： [1 2 0 0 0 0]

3 ：入栈 1 次： [1 2 0 0 0 0 3]

此时栈中元素个数和数组元素个数相等，重新写入数组即可。

再举一个例子，对于数组 [1 2 0 0 3 0 4 5]

1 ：入栈 1 次： [1]

2 ：入栈 1 次： [1 2]

0 ：入栈 2 次： [1 2 0 0]

0 ：入栈 2 次： [1 2 0 0 0 0]

3 ：入栈 1 次： [1 2 0 0 0 0 3]

0 ：入栈 2 次： [1 2 0 0 0 0 3 0 0]

此时栈中元素个数比数组元素个数多一个，需要去掉最后一个零，把 [1 2 0 0 0 0 3 0] 写入数组。

由于不允许开辟 O(N) 的额外空间，我们可以考虑用 top 来维护栈顶（即栈中的有效数据个数），模拟出入栈过程。假设数组长度为 n ，当 top<n 时，可以继续入栈。

用下标 i 来记录要复写的元素，下标 j 来记录复写的目标位置。在前面模拟入栈的过程中，可以记录最后一个入栈的元素在数组中的下标，即 i 。由于是从后向前复写， j 要初始化为 n-1 。

对于栈中元素个数比数组元素个数多一个，即 top==n+1 的特殊情况，最后一个零只需要复写一次，其余情况正常复写即可。复写时，把 [0,i] 的元素按照是否为零进行分类，非零元素复写一次，零复写两次。

// 方法一：双指针
class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        int n = arr.size();
        int top = 0; // 记录栈顶
        int i = -1;
        // 模拟把数组元素放入栈中
        while (top < n)
        {
            if (arr[++i])
            {
                ++top;
            }
            else
            {
                top += 2;
            }
        }

        // i 表示要复写的数据
        // j 表示要复写的位置
        int j = n - 1;
        // 最后放入 2 个零导致栈中元素比数组多
        if (top == n + 1)
        {
            arr[j--] = 0;
            --i;
        }

        while (j > 0)
        {
            // 第一次复写
            arr[j--] = arr[i];
            // 零还需要复写第二次
            if (arr[i--] == 0)
            {
                arr[j--] = 0;
            }
        }
    }
};