【C语言刷LeetCode】735. 行星碰撞(M)

【

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

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

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

示例 1：

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

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。
示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
 

提示：

2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/asteroid-collision
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

】

看题意很容易想到单调栈，但却读错了题意两次，所以做题前先读三次题意，好好理解一下。

因为碰撞时要么消失要么不改变大小，所以栈中元素的处理idx索引要小心。

 栈顶元素为右，当前为左才会碰撞。所以判断碰撞后的结果，可以用两个元素求和。

int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
    int *stack = NULL;
    int idx = -1; // idx 指向存放元素的位置
    int i;
    int flag = 1; // 上一个元素的方向，1:右；-1：左

    stack = (int *)malloc(sizeof(int) * asteroidsSize);
    memset(stack, 0, sizeof(int) * asteroidsSize);

    stack[++idx] = asteroids[0];

    for (i = 1; i < asteroidsSize; i++) {
        int comp = -1;

        // 栈顶元素为右，当前为左才会碰撞
        while (asteroids[i] < 0 && idx > -1 && stack[idx] > 0) {
            comp = stack[idx] + asteroids[i];  // 和栈顶元素比较正负
            if (comp < 0) {
                idx--; // 栈顶元素爆炸了
                continue;
            } else if (comp == 0) {
                idx--;
                break;
            } else {
                break;
            }
        }

        if (comp < 0) {
            stack[++idx] = asteroids[i]; // 把当前元素放进去
        }
    }

    *returnSize = idx + 1;
    return stack;
}
/*
1. 又一次看错题意了，较小的会爆炸，而不是大减小,一些代码又要重新调了
2. 理解错题意了。以为第一个左，第二个右也会相撞，我理解[-2,-1,1,2] 的返回值是空，结果正确的返回值是[-2,-1,1,2],把题目搞复杂了 
3. flag 判断时需要注意idx

这一次不把元素拿出来，直接比较
*/