LeetCode 每日一题笔记 日期：2026.05.31 题目：2126. 摧毁小行星

LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.31
• 题目：2126. 摧毁小行星
• 难度：中等
• 标签：数组、贪心、排序

1. 题目理解

问题描述：
给定行星初始质量mass和小行星数组asteroids，可以按任意顺序与小行星碰撞：

• 行星质量 ≥ 小行星质量：行星摧毁小行星，并获得其质量；
• 行星质量 < 小行星质量：行星被摧毁。
  判断是否存在一种顺序，让行星摧毁所有小行星。

示例：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true
解释：按 [3,5,9,19,21] 的顺序，行星质量依次增长为 13→18→27→46→67，可全部摧毁。

2. 解题思路

核心观察

• 贪心策略：优先摧毁质量小的小行星，才能不断增长行星质量，为后续摧毁更大的小行星创造条件；
• 排序后遍历，只要过程中行星质量始终不小于当前小行星，就能完成全部摧毁。

算法步骤

1. 将小行星数组按升序排序；
2. 用long类型记录行星当前质量，避免溢出；
3. 遍历排序后的数组，若行星质量小于当前小行星，直接返回false；
4. 否则累加小行星质量，遍历结束返回true。

3. 代码实现

packagelc2126;importjava.util.Arrays;classSolution{publicbooleanasteroidsDestroyed(intmass,int[]asteroids){Arrays.sort(asteroids);longcur=mass;for(inta:asteroids){if(cur<a)returnfalse;cur+=a;}returntrue;}}

4. 代码优化说明

（代码未做任何修改，仅添加注释讲解）

classSolution{publicbooleanasteroidsDestroyed(intmass,int[]asteroids){// 找到所有小行星中的最大质量，用于确定二进制分组的最高位intmx=0;for(intx:asteroids){mx=Math.max(mx,x);}// 计算最大质量的二进制位数，确定分组数量intmaxWidth=32-Integer.numberOfLeadingZeros(mx);// sum数组：存储每个二进制位分组内所有小行星的质量和long[]sum=newlong[maxWidth];// mn数组：存储每个二进制位分组内的最小小行星质量int[]mn=newint[maxWidth];Arrays.fill(mn,Integer.MAX_VALUE);// 按二进制最高位对小行星进行分组for(intx:asteroids){// 计算当前小行星的最高二进制位inti=31-Integer.numberOfLeadingZeros(x);sum[i]+=x;mn[i]=Math.min(mn[i],x);}// 行星当前质量，用long避免溢出longm=mass;// 按二进制位从低到高遍历分组for(inti=0;i<maxWidth;i++){// 该分组无小行星，跳过if(mn[i]==Integer.MAX_VALUE){continue;}// 行星质量小于该分组最小的小行星，无法摧毁，直接返回falseif(m<mn[i]){returnfalse;}// 摧毁该分组所有小行星，累加质量m+=sum[i];}// 所有分组都可摧毁，返回truereturntrue;}}

5. 复杂度分析

• 排序贪心解法
  • 时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)，排序占主要开销，遍历为线性。
  • 空间复杂度：O(1)O(1)O(1)，原地排序（不考虑排序栈开销），仅用常数变量。
• 二进制分组优化解法
  • 时间复杂度：O(n)O(n)O(n)，两次线性遍历，无排序开销。
  • 空间复杂度：O(log⁡M)O(\log M)O(logM)，MMM为最大小行星质量，分组数组大小为常数级。

6. 总结

• 核心：贪心思想，优先处理质量小的目标，是解决此类“增长型”问题的通用策略；
• 排序解法直观易写，面试优先使用；二进制分组解法在大数据下效率更高，可作为进阶优化；
• 关键细节：行星质量累加可能超过int范围，需用long类型存储，避免溢出错误。