LeetCode LCR 037. 行星碰撞

Categories:

题目描述
思路分析
1. 解法一：栈模拟（推荐）
相似题目

题目描述

✅ LCR 037. 行星碰撞

思路分析

解法一：栈模拟（推荐）

核心思路：

用栈维护当前仍存在的小行星。

只有“栈顶向右 + 当前向左”才会发生碰撞。

持续比较直到分出胜负：相等则同时消失，质量小者消失，质量大者保留。

复杂度分析：

时间复杂度：O(n)，其中 n 表示小行星数量，每个元素最多进栈出栈一次。

空间复杂度：O(n)，栈的额外空间。

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int a : asteroids) {
            boolean alive = true;
            while (alive && a < 0 && !stack.isEmpty() && stack.peekLast() > 0) {
                int top = stack.peekLast();
                if (top < -a) {
                    stack.pollLast();
                    continue;
                }
                if (top == -a) {
                    stack.pollLast();
                }
                alive = false;
            }
            if (alive) {
                stack.addLast(a);
            }
        }

        int[] res = new int[stack.size()];
        int idx = 0;
        for (int v : stack) {
            res[idx++] = v;
        }
        return res;
    }
}

func asteroidCollision(asteroids []int) []int {
    stack := []int{}
    for _, a := range asteroids {
        alive := true
        for alive && a < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
            top := stack[len(stack)-1]
            if top < -a {
                stack = stack[:len(stack)-1]
                continue
            }
            if top == -a {
                stack = stack[:len(stack)-1]
            }
            alive = false
        }
        if alive {
            stack = append(stack, a)
        }
    }
    return stack
}

相似题目

题目	难度	考察点
84. 柱状图中最大的矩形	困难	单调栈
503. 下一个更大元素 II	中等	单调栈
739. 每日温度	中等	单调栈
901. 股票价格跨度	中等	单调栈
1047. 删除字符串中的所有相邻重复项	简单	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/72303611