第57天。
今天的题目是Asteroid Collision:
用栈去模拟整个过程，因为STL中的栈没法直接顺序迭代出来，所以我们用vector模拟一个栈出来使用。
不难发现，最终的结果一定是小于 0 的值在前面，而大于 0 的值在后面，所以我们只用栈维护大于 0 的值。而小于 0 的值如果前面没有 大于 0 的值的话（即已经确定没有碰撞后），直接将其放入答案中。又因为我们是用vector进行的模拟，所以可以在维护栈顶指针的时候也维护一个栈底指针来实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| vector<int> asteroidCollision(vector<int>& asteroids) {
int size = asteroids.size();
if (size == 0) return vector<int>();
vector<int> st(size);
int top, beg;
for(beg = 0;beg < size && asteroids[beg] < 0; beg++) st[beg] = asteroids[beg];
top = beg;
for(int i = beg; i < size;i++) {
int a = asteroids[i];
if (top == beg) {
st[top++] = a;
if (a < 0) beg++;
}
else if (a > 0) st[top++] = a;
else if (st[top-1] == -a) top--;
else if (st[top-1] > -a) ;
else {
while(top != beg && st[top-1] < -a)
top--;
if (top != beg && st[top-1] == -a) top--;
else if (top == beg) {
st[top] = a;
top = beg = beg + 1;
}
}
}
return vector<int>(st.begin(), st.begin() + top);
}
|