LCR 037-行星碰撞

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给定一个整数数组 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 。

示例 4：

**输入：** asteroids = [-2,-1,1,2]
**输出：** [-2,-1,1,2]
**解释** **：** -2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。

提示：

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

注意：本题与主站 735 题相同： https://leetcode-cn.com/problems/asteroid-collision/

方法一：栈模拟

使用栈 st 模拟小行星碰撞，从左往右遍历小行星数组 asteroids，当我们遍历到小行星 aster 时，使用变量 alive 记录小行星 aster 是否还存在（即未爆炸）。

当小行星 aster 存在且 aster} < 0，栈顶元素非空且大于 0 时，说明两个小行星相互向对方移动：如果栈顶元素大于等于 -\textit{aster，则小行星 aster 发生爆炸，将 alive 置为 false；如果栈顶元素小于等于 -\textit{aster，则栈顶元素表示的小行星发生爆炸，执行出栈操作。重复以上判断直到不满足条件，如果最后 alive 为真，说明小行星 aster 不会爆炸，则将 aster 入栈。

为了代码简洁性，我们使用变长数组模拟栈。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = []
        for aster in asteroids:
            alive = True
            while alive and aster < 0 and st and st[-1] > 0:
                alive = st[-1] < -aster
                if st[-1] <= -aster:
                    st.pop()
            if alive:
                st.append(aster)
        return st
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> st;
        for (auto aster : asteroids) {
            bool alive = true;
            while (alive && aster < 0 && !st.empty() && st.back() > 0) {
                alive = st.back() < -aster; // aster 是否存在
                if (st.back() <= -aster) {  // 栈顶小行星爆炸
                    st.pop_back();
                }
            }
            if (alive) {
                st.push_back(aster);
            }
        }
        return st;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int aster : asteroids) {
            boolean alive = true;
            while (alive && aster < 0 && !stack.isEmpty() && stack.peek() > 0) {
                alive = stack.peek() < -aster; // aster 是否存在
                if (stack.peek() <= -aster) {  // 栈顶小行星爆炸
                    stack.pop();
                }
            }
            if (alive) {
                stack.push(aster);
            }
        }
        int size = stack.size();
        int[] ans = new int[size];
        for (int i = size - 1; i >= 0; i--) {
            ans[i] = stack.pop();
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        Stack<int> stack = new Stack<int>();
        foreach (int aster in asteroids) {
            bool alive = true;
            while (alive && aster < 0 && stack.Count > 0 && stack.Peek() > 0) {
                alive = stack.Peek() < -aster; // aster 是否存在
                if (stack.Peek() <= -aster) {  // 栈顶小行星爆炸
                    stack.Pop();
                }
            }
            if (alive) {
                stack.Push(aster);
            }
        }
        int count = stack.Count;
        int[] ans = new int[count];
        for (int i = count - 1; i >= 0; i--) {
            ans[i] = stack.Pop();
        }
        return ans;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
    int *st = (int *)malloc(sizeof(int) * asteroidsSize);
    int pos = 0;
    for (int i = 0; i < asteroidsSize; i++) {
        bool alive = true;
        while (alive && asteroids[i] < 0 && pos > 0 && st[pos - 1] > 0) {
            alive = st[pos - 1] < -asteroids[i]; // aster 是否存在
            if (st[pos - 1] <= -asteroids[i]) {  // 栈顶小行星爆炸
                pos--;
            }
        }
        if (alive) {
            st[pos++] = asteroids[i];
        }
    }
    *returnSize = pos;
    return st;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var asteroidCollision = function(asteroids) {
    const stack = [];
    for (const aster of asteroids) {
        let alive = true;
        while (alive && aster < 0 && stack.length > 0 && stack[stack.length - 1] > 0) {
            alive = stack[stack.length - 1] < -aster; // aster 是否存在
            if (stack[stack.length - 1] <= -aster) {  // 栈顶小行星爆炸
                stack.pop();
            }
        }
        if (alive) {
            stack.push(aster);
        }
    }
    const size = stack.length;
    const ans = new Array(size).fill(0);
    for (let i = size - 1; i >= 0; i--) {
        ans[i] = stack.pop();
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func asteroidCollision(asteroids []int) (st []int) {
    for _, aster := range asteroids {
        alive := true
        for alive && aster < 0 && len(st) > 0 && st[len(st)-1] > 0 {
            alive = st[len(st)-1] < -aster // aster 是否存在
            if st[len(st)-1] <= -aster {   // 栈顶小行星爆炸
                st = st[:len(st)-1]
            }
        }
        if alive {
            st = append(st, aster)
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组 asteroids 的大小。出入栈次数均不超过 n 次。

  • 空间复杂度：O(1)。返回值不计入空间复杂度。

 Comments
On this page
LCR 037-行星碰撞