What is the main pattern used in the 'Destroying Asteroids' problem?

The main pattern used in the 'Destroying Asteroids' problem is a greedy approach, where you select the smallest asteroid that can be destroyed to maximize the planet's growth in mass.

Can the asteroids be destroyed in any order?

No, the asteroids must be destroyed in an order where the planet’s mass is greater than or equal to the asteroid's mass at every step. Sorting the asteroids helps with this.

What is the optimal way to approach the 'Destroying Asteroids' problem?

The optimal way is to sort the asteroids in increasing order and then check if the planet’s mass is sufficient to destroy each asteroid, updating the planet’s mass accordingly.

How does GhostInterview assist with solving the 'Destroying Asteroids' problem?

GhostInterview helps by providing step-by-step guidance on the greedy approach and optimizing the solution with early termination for better performance.

What are common mistakes when solving the 'Destroying Asteroids' problem?

Common mistakes include not sorting the asteroids, failing to handle edge cases, and not correctly applying the greedy approach for optimal asteroid selection.

#2126

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

摧毁小行星

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。你可以按任意顺序重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量大于等于小行星的质量，那么小行星被摧毁，并且行星会…

数组贪心排序

题目描述

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被摧毁，并且行星会获得这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星都能被摧毁，请返回 true ，否则返回 false 。

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：一种安排小行星的方式为 [9,19,5,3,21] ：
- 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
- 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
- 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
- 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
- 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67
所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]
输出：false
解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

提示：

1 <= mass <= 10⁵
1 <= asteroids.length <= 10⁵
1 <= asteroids[i] <= 10⁵

lightbulb

解题思路

方法一：排序 + 贪心

根据题目描述，我们可以将小行星按质量从小到大排序，然后依次遍历小行星，如果行星的质量小于小行星的质量，那么行星将被摧毁，返回 false，否则行星将获得这颗小行星的质量。

如果所有小行星都能被摧毁，返回 true。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是小行星的数量。

1

2

3

4

5

6

7

8

9

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()
        for x in asteroids:
            if mass < x:
                return False
            mass += x
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate is expected to grasp the greedy approach and its application to the problem.
question_mark
They should be able to justify why sorting the array helps simplify the solution.
question_mark
The interviewer may want to see how the candidate handles early termination to improve efficiency.

warning

常见陷阱

外企场景

error
A common mistake is not sorting the asteroids first, which leads to suboptimal solutions and increased complexity.
error
Failing to handle edge cases, such as the planet having insufficient mass to destroy the largest asteroid, can result in incorrect answers.
error
Misunderstanding the greedy approach may lead to choosing asteroids in the wrong order, causing the planet to be destroyed prematurely.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the planet has a fixed number of asteroid collisions allowed? The problem could be adjusted to account for a limited number of successful collisions.
arrow_right_alt
What if asteroids can be destroyed in any order, not just by increasing mass? This would remove the greedy choice pattern and require a different approach.
arrow_right_alt
What if there are multiple planets with different masses trying to destroy the same asteroids? This could require a more complex simulation with multiple greedy selections.

help

常见问题

外企场景

继续练习

#2136 全部开花的最早一天 #2141 同时运行 N 台电脑的最长时间 #2144 打折购买糖果的最小开销