Medium

题目描述

给你一个整数 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^5
  • 1 <= asteroids.length <= 10^5
  • 1 <= asteroids[i] <= 10^5

解题思路

这道题的核心思想是贪心算法。为了最大化摧毁小行星的可能性，我们需要采用最优的碰撞顺序。

解题思路：

  1. 排序策略：将所有小行星按质量从小到大排序。这样可以确保我们总是优先碰撞质量最小的小行星。

  2. 贪心选择：每次都选择当前能够摧毁的质量最小的小行星。如果连最小的小行星都无法摧毁，那么更大的小行星也无法摧毁，直接返回 false。

  3. 质量累积：成功摧毁一颗小行星后，行星质量会增加，这为后续摧毁更大质量的小行星创造了条件。

  4. 数据类型注意：由于质量可能累积得很大（最坏情况下可达 10^5 + 10^5 × 10^5 = 10^10），需要使用 long long 类型避免整数溢出。

算法流程：

  • 对小行星数组进行排序
  • 遍历排序后的数组，逐一检查是否能摧毁当前小行星
  • 如果能摧毁，累加质量；如果不能，直接返回 false
  • 如果所有小行星都能被摧毁，返回 true

这种贪心策略是最优的，因为如果当前最小的小行星都无法摧毁，那么剩余的更大小行星也不可能被摧毁。

代码实现

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        sort(asteroids.begin(), asteroids.end());
        long long currentMass = mass;
        
        for (int asteroid : asteroids) {
            if (currentMass >= asteroid) {
                currentMass += asteroid;
            } else {
                return false;
            }
        }
        
        return true;
    }
};

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

public class Solution {
    public bool AsteroidsDestroyed(int mass, int[] asteroids) {
        Array.Sort(asteroids);
        long currentMass = mass;
        
        foreach (int asteroid in asteroids) {
            if (currentMass >= asteroid) {
                currentMass += asteroid;
            } else {
                return false;
            }
        }
        
        return true;
    }
}

var asteroidsDestroyed = function(mass, asteroids) {
    asteroids.sort((a, b) => a - b);
    let currentMass = mass;
    
    for (let asteroid of asteroids) {
        if (currentMass >= asteroid) {
            currentMass += asteroid;
        } else {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要消耗在排序操作，其中 n 是小行星数量
空间复杂度O(1)只使用常数额外空间（排序为原地排序）

相关题目