Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 735. Asteroid Collision 行星碰撞

We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

2、解题思路：

本题可以使用栈的数据结构：小行星的碰撞过程满足后进先出的原则。当我们遍历小行星数组时，需要根据它们的方向来决定是推入栈中还是从栈中弹出。如果小行星的方向是向左的，就直接将其推入栈中；如果小行星的方向是向右的，就需要考虑与栈中的小行星是否会碰撞。而栈正好满足后进先出的特点，可以保证每次从栈中弹出的小行星是最近与当前小行星相遇的小行星。

3、代码

import java.util.*;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        // 创建一个栈，用于模拟碰撞过程
        Stack<Integer> stack = new Stack<>();
        
        for (int asteroid : asteroids) {
            if (asteroid > 0) {
                // 当前asteroid向右移动，入栈 
                stack.push(asteroid);
            } else {
                // 当前asteroid向左移动, 检查是否有碰撞
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroid) {
                    // 如果栈顶 asteroid 比当前 asteroid 小，将其弹出
                    stack.pop();
                }
                
                if (stack.isEmpty() || stack.peek() < 0) {
                    // 如果栈为空，或者栈顶 asteroid 正在向左移动，将当前asteroid入栈
                    stack.push(asteroid);
                } else if (stack.peek() == -asteroid) {
                    // 如果栈顶 asteroid 与当前 asteroid 相等，都爆炸
                    stack.pop();
                }
            }
        }
        
        // 将栈中元素逆序输出到结果数组
        int[] result = new int[stack.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        
        return result;
    }
}