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. 解题思路核心观察贪心策略优先摧毁质量小的小行星才能不断增长行星质量为后续摧毁更大的小行星创造条件排序后遍历只要过程中行星质量始终不小于当前小行星就能完成全部摧毁。算法步骤将小行星数组按升序排序用long类型记录行星当前质量避免溢出遍历排序后的数组若行星质量小于当前小行星直接返回false否则累加小行星质量遍历结束返回true。3. 代码实现packagelc2126;importjava.util.Arrays;classSolution{publicbooleanasteroidsDestroyed(intmass,int[]asteroids){Arrays.sort(asteroids);longcurmass;for(inta:asteroids){if(cura)returnfalse;cura;}returntrue;}}4. 代码优化说明代码未做任何修改仅添加注释讲解classSolution{publicbooleanasteroidsDestroyed(intmass,int[]asteroids){// 找到所有小行星中的最大质量用于确定二进制分组的最高位intmx0;for(intx:asteroids){mxMath.max(mx,x);}// 计算最大质量的二进制位数确定分组数量intmaxWidth32-Integer.numberOfLeadingZeros(mx);// sum数组存储每个二进制位分组内所有小行星的质量和long[]sumnewlong[maxWidth];// mn数组存储每个二进制位分组内的最小小行星质量int[]mnnewint[maxWidth];Arrays.fill(mn,Integer.MAX_VALUE);// 按二进制最高位对小行星进行分组for(intx:asteroids){// 计算当前小行星的最高二进制位inti31-Integer.numberOfLeadingZeros(x);sum[i]x;mn[i]Math.min(mn[i],x);}// 行星当前质量用long避免溢出longmmass;// 按二进制位从低到高遍历分组for(inti0;imaxWidth;i){// 该分组无小行星跳过if(mn[i]Integer.MAX_VALUE){continue;}// 行星质量小于该分组最小的小行星无法摧毁直接返回falseif(mmn[i]){returnfalse;}// 摧毁该分组所有小行星累加质量msum[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类型存储避免溢出错误。