LeetCode 735. 小行星碰撞

Categories:

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

题目描述

✅ 735. 小行星碰撞

思路分析

解法一：栈模拟碰撞（推荐）

核心思路：

只会在“右向”与“左向”相遇时发生碰撞。

使用栈存放仍在飞行的小行星，遇到左向小行星时与栈顶右向小行星持续比较。

根据大小决定弹栈、同归于尽或当前小行星被消灭。

复杂度分析：

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

空间复杂度：O(n)，其中 n 表示栈的大小。

import java.util.*;

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (int a : asteroids) {
            boolean alive = true;
            if (a > 0) {
                stack.push(a);
                continue;
            }

            while (alive && !stack.isEmpty() && stack.peek() > 0) {
                int top = stack.peek();
                if (top < -a) {
                    stack.pop();
                    continue;
                }
                if (top == -a) {
                    stack.pop();
                }
                alive = false;
            }

            if (alive) {
                stack.push(a);
            }
        }

        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}

func asteroidCollision(asteroids []int) []int {
	stack := make([]int, 0)

	for _, a := range asteroids {
		alive := true
		if a > 0 {
			stack = append(stack, a)
			continue
		}

		for alive && 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
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈
32. 最长有效括号	困难	栈、动态规划
150. 逆波兰表达式求值	中等	栈
394. 字符串解码	中等	栈
402. 移掉 K 位数字	中等	栈、贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/74257874