Medium

题目描述

给定一个整数数组 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 = [3,5,-6,2,-1,4]
输出：[-6,2,4]
解释：小行星 -6 使 3 和 5 爆炸，然后继续向左移动。另一边，小行星 2 使 -1 爆炸并继续向右移动，但不会到达 4。

提示：

  • 2 <= asteroids.length <= 10^4
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0

解题思路

解题思路

这道题需要模拟小行星碰撞的过程，关键是理解碰撞的条件：只有当向右移动的小行星遇到向左移动的小行星时才会发生碰撞。

栈解法（推荐）

使用栈来模拟碰撞过程：

  1. 遍历小行星数组，对于每个小行星：
    • 如果是正数（向右移动），直接入栈
    • 如果是负数（向左移动），需要检查是否与栈顶的正数小行星碰撞
  2. 碰撞处理：
    • 如果当前负数小行星大小大于栈顶正数小行星，栈顶爆炸，继续检查下一个栈顶
    • 如果大小相等，两个都爆炸
    • 如果当前负数小行星较小，当前小行星爆炸

时间复杂度分析

虽然有嵌套循环，但每个小行星最多被处理两次（入栈和出栈），所以时间复杂度是 O(n)。

边界情况

  • 栈为空或栈顶是负数时，负数小行星直接入栈
  • 连续的正数或负数小行星不会碰撞

代码实现

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> stack;
        
        for (int asteroid : asteroids) {
            bool exploded = false;
            
            while (!stack.empty() && stack.back() > 0 && asteroid < 0) {
                if (stack.back() < -asteroid) {
                    stack.pop_back();
                } else if (stack.back() == -asteroid) {
                    stack.pop_back();
                    exploded = true;
                    break;
                } else {
                    exploded = true;
                    break;
                }
            }
            
            if (!exploded) {
                stack.push_back(asteroid);
            }
        }
        
        return stack;
    }
};

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        
        for asteroid in asteroids:
            exploded = False
            
            while stack and stack[-1] > 0 and asteroid < 0:
                if stack[-1] < -asteroid:
                    stack.pop()
                elif stack[-1] == -asteroid:
                    stack.pop()
                    exploded = True
                    break
                else:
                    exploded = True
                    break
            
            if not exploded:
                stack.append(asteroid)
        
        return stack

public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        List<int> stack = new List<int>();
        
        foreach (int asteroid in asteroids) {
            bool exploded = false;
            
            while (stack.Count > 0 && stack[stack.Count - 1] > 0 && asteroid < 0) {
                if (stack[stack.Count - 1] < -asteroid) {
                    stack.RemoveAt(stack.Count - 1);
                } else if (stack[stack.Count - 1] == -asteroid) {
                    stack.RemoveAt(stack.Count - 1);
                    exploded = true;
                    break;
                } else {
                    exploded = true;
                    break;
                }
            }
            
            if (!exploded) {
                stack.Add(asteroid);
            }
        }
        
        return stack.ToArray();
    }
}

var asteroidCollision = function(asteroids) {
    const stack = [];
    
    for (let asteroid of asteroids) {
        let exploded = false;
        
        while (stack.length > 0 && asteroid < 0 && stack[stack.length - 1] > 0) {
            const top = stack[stack.length - 1];
            
            if (Math.abs(asteroid) > top) {
                stack.pop();
            } else if (Math.abs(asteroid) === top) {
                stack.pop();
                exploded = true;
                break;
            } else {
                exploded = true;
                break;
            }
        }
        
        if (!exploded) {
            stack.push(asteroid);
        }
    }
    
    return stack;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
栈模拟O(n)O(n)

说明：

  • 时间复杂度：O(n)，每个小行星最多被处理两次（入栈和出栈）
  • 空间复杂度：O(n)，栈最多存储所有小行星

相关题目