方法一：双指针法
从前向后复写，会造成覆盖。所以，应该从后向前复写，这样我们可以考虑维护一个栈。遍历数组，如果遇到非0元素，就入栈1次；如果遇到0，就入栈2次。当栈中的元素个数超出数组的元素个数时，把栈中的元素重新从后向前写入数组即可。
如：对于数组[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个，需要去掉最后一个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只需要复写1次，其余情况正常复写即可。复写时，把[0,i]的元素按照是否为0进行分类，非零元素复写1次，零复写2次。
// 方法一：双指针
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个0导致栈中元素比数组多
if (top == n + 1)
{
arr[j--] = 0;
--i;
}
// while(j>=0)也可以，但是第一个位置是否复写没有区别
while (j > 0)
{
arr[j--] = arr[i];
if (arr[i] == 0)
{
arr[j--] = 0;
}
--i;
}
}
};
