leetcode_735. 行星碰撞

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

单调栈思想， 注意分类， while 循环是关键，

两种做法： 一个是单调栈的经典思路， 另外一个是也是栈， 但是只比较最top 的两个小球，也比较巧妙

解法1：

 1 int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
 2     int *stack = (int *)malloc(sizeof(int) * asteroidsSize);
 3     int top = -1;
 4     int add = 0;
 5     int push_flag;
 6 
 7     for(int i = 0; i < asteroidsSize; i++) {
 8         if(top == -1 || asteroids[i] > 0) {
 9             stack[++top] = asteroids[i];
10         } else {
11             push_flag = 1;
12             // 只有 asteroids[i] > 0 && stack[top] > 0 这一种情况才会比较
13             while(top > -1 && stack[top] > 0) {
14                 add = stack[top] + asteroids[i];
15                 if(add < 0) {
16                     top--;
17                     push_flag = 1;
18                 } else if(add == 0) {
19                     top--;
20                     push_flag = 0;
21                     break;
22                 }else {
23                     push_flag = 0;
24                     break;
25                 }
26             }
27             if(push_flag == 1) {
28                 stack[++top] = asteroids[i];
29             }
30         }
31     }
32     *returnSize = top + 1;
33     return stack;
34 }

方法2：

 1 // 所以我们的方法是 只循环比较栈顶两个元素  ，
 2 int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
 3     int *res = (int *)malloc(sizeof(int) * asteroidsSize);
 4     if(res == NULL) {
 5         return NULL;
 6     }
 7     memset(res, 0, sizeof(int) * asteroidsSize);
 8 
 9     int top = 0;
10     int tmp = 0;
11     for (int i = 0; i < asteroidsSize; i++) {
12         res[top] = asteroids[i];
13         top++;
14         // 循环比较栈顶两个元素, 当栈顶是 6  -5 这种一正一负情况才会发生碰撞
15         while(top >= 2 && res[top -2] > 0 && res[top - 1] < 0){
16             tmp = res[top -2] + res[top - 1];
17             if(tmp > 0) {
18                 top--;
19             }else if(tmp ==0) {
20                 top-=2;
21             }else{
22                 res[top -2] = res[top - 1];
23                 top--;
24             }
25         }
26     }
27     *returnSize = top;
28     return res;
29 }