当前位置：首页 > news >正文

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

news 2026/5/31 22:45:00

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);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为最大小行星质量，分组数组大小为常数级。