LCR 037-行星碰撞

Raphael Liu Lv10

给定一个整数数组 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-行星碰撞