-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAsteroidCollision.java
More file actions
64 lines (61 loc) · 2.3 KB
/
AsteroidCollision.java
File metadata and controls
64 lines (61 loc) · 2.3 KB
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package com.leetcode.stack;
import java.util.Stack;
public class AsteroidCollision {
/***
* 给定一个整数数组 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<= 10^4
* -1000 <= asteroids[i] <= 1000
* asteroids[i] != 0
* 链接：https://leetcode.cn/problems/asteroid-collision
* @param asteroids
* @return
*/
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
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;
}
}