Code & Func

第57天。

用栈去模拟整个过程，因为STL中的栈没法直接顺序迭代出来，所以我们用vector模拟一个栈出来使用。

不难发现，最终的结果一定是小于 0 的值在前面，而大于 0 的值在后面，所以我们只用栈维护大于 0 的值。而小于 0 的值如果前面没有大于 0 的值的话（即已经确定没有碰撞后），直接将其放入答案中。又因为我们是用vector进行的模拟，所以可以在维护栈顶指针的时候也维护一个栈底指针来实现：

1
vector<int> asteroidCollision(vector<int>& asteroids) {
2
    int size = asteroids.size();
3
    if (size == 0) return vector<int>();
4
    vector<int> st(size);
5
    int top, beg;
6
    for(beg = 0;beg < size && asteroids[beg] < 0; beg++) st[beg] = asteroids[beg];
7
    top = beg;
8
    for(int i = beg; i < size;i++) {
9
        int a = asteroids[i];
10
        if (top == beg) {
11
            st[top++] = a;
12
            if (a < 0) beg++;
13
        }
14
        else if (a > 0) st[top++] = a;
15
        else if (st[top-1] == -a) top--;
13 collapsed lines
16
        else if (st[top-1] > -a) /* do nothing */;
17
        else {
18
            while(top != beg && st[top-1] < -a)
19
                top--;
20
            if (top != beg && st[top-1] == -a) top--;
21
            else if (top == beg) {
22
                st[top] = a;
23
                top = beg = beg + 1;
24
            }
25
        }
26
    }
27
    return vector<int>(st.begin(), st.begin() + top);
28
}