其他系列文章导航
Java基础合集
数据结构与算法合集设计模式合集
多线程合集
分布式合集
ES合集
这是力扣的 735 题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。
慢慢开始栈的模块了，这道题是一道非常好的栈的例题，很有代表性。
给定一个整数数组
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
栈是一种数据结构，其特点是后进先出（Last In First Out，LIFO）。在算法中，栈在很多情况下是非常有用的，下面是一些常见的情况：
这只是栈在算法中的一些应用，实际上还有很多其他的应用场景。
思路与算法：
由于碰撞抵消总是从相邻行星之间发生，我们可以使用「栈」来模拟该过程。
从前往后处理所有的 asteroids[i] ，使用栈存储当前未被抵消的行星，当栈顶元素方向往右，当前 asteroids[i] 方向往左时，会发生抵消操作，抵消过程根据规则进行即可。
用到变量 ok 的 true 和 false 来表示待插入栈的元素是否还大于栈顶元素。
最后把栈内元素再放入 int[] 中。
Java版本：
class Solution {
public static int[] asteroidCollision(int[] asteroids) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
for (int i : asteroids) {
boolean ok = true;
while (ok && !deque.isEmpty() && deque.peekLast() > 0 && i < 0) {
int a = deque.peekLast(), b = -i;
if (a <= b) deque.pollLast();
if (a >= b) ok = false;
}
if (ok) deque.addLast(i);
}
int n = deque.size();
int[] res = new int[n];
while(!deque.isEmpty()) res[--n]=deque.pollLast();
return res;
}
}C++版本：
class Solution {
public:
static vector<int> asteroidCollision(vector<int>& asteroids) {
deque<int> deque;
for (int i : asteroids) {
bool ok = true;
while (ok && !deque.empty() && deque.back() > 0 && i < 0) {
int a = deque.back(), b = -i;
if (a <= b) deque.pop_back();
if (a >= b) ok = false;
}
if (ok) deque.push_back(i);
}
vector<int> res(deque.begin(), deque.end());
return res;
}
};
Python版本：
from collections import deque
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
deque = deque()
for i in asteroids:
ok = True
while ok and deque and deque[-1] > 0 and i < 0:
a, b = deque[-1], -i
if a <= b:
deque.pop()
if a >= b:
ok = False
if ok:
deque.append(i)
return list(deque)
Go版本：
package main
import "fmt"
func asteroidCollision(asteroids []int) []int {
var stack []int
for _, i := range asteroids {
ok := true
for ok && len(stack) > 0 && stack[len(stack)-1] > 0 && i < 0 {
a, b := stack[len(stack)-1], -i
if a <= b {
stack = stack[:len(stack)-1]
}
if a >= b {
ok = false
}
}
if ok {
stack = append(stack, i)
}
}
return stack
}
func main() {
asteroids := []int{5, 10, -5}
fmt.Println(asteroidCollision(asteroids))
}