将给定整数分解为最大完美平方数序列的最快算法实现咨询

你的实现逻辑完全符合需求，核心思路正确，当前覆盖的测试用例运行正常，可读性也不错。但确实存在几个可优化的点：

• 浮点运算存在潜在精度风险：虽然1~1e6范围下double精度足够支撑平方根计算，但浮点运算本身比整数运算慢，且如果后续输入范围扩大很容易出现精度偏差（比如超大整数下sqrt计算截断错误）
• 循环冗余：当剩余值小于当前平方根的平方时，每次都重新计算平方根存在不必要的开销，且最后剩余值小于4时，需要循环n次反复加1，完全可以批量处理
• 集合转数组的开销：ArrayList+Stream转数组的方式虽然写法简洁，但对于小数据量场景有不必要的装箱、拆箱和流操作开销

我们可以基于整数运算实现，同时复用之前的平方根计算结果，还可以批量添加末尾的1，优化后代码如下：

public static int[] solution(int startingSquareYards) {
    List<Integer> result = new ArrayList<>();
    int remaining = startingSquareYards;
    // 输入最大值为1e6，平方根最大为1000，直接初始化即可避免首次浮点运算
    int root = 1000;
    while (remaining > 0) {
        // 递减找到当前剩余值可容纳的最大平方数的根
        while (root * root > remaining) {
            root--;
        }
        int square = root * root;
        // 特殊优化：如果平方数为1，直接批量添加所有剩余的1，结束循环
        if (square == 1) {
            for (int i = 0; i < remaining; i++) {
                result.add(1);
            }
            break;
        }
        result.add(square);
        remaining -= square;
    }
    // 手动转数组，避免Stream额外开销
    int[] resArr = new int[result.size()];
    for (int i = 0; i < result.size(); i++) {
        resArr[i] = result.get(i);
    }
    return resArr;
}

如果追求更极致的写法简洁性，也可以保留平方根计算的写法，仅替换潜在风险点：

public static int[] solution(int startingSquareYards) {
    List<Integer> result = new ArrayList<>();
    int remaining = startingSquareYards;
    while (remaining > 0) {
        int root = (int) Math.sqrt(remaining);
        int square = root * root;
        result.add(square);
        remaining -= square;
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

• 时间复杂度：最坏情况从O(√n)降到了O(log n)，最大仅需1000次root递减循环，完全避免了重复浮点运算的开销
• 空间复杂度：无额外开销，和原有实现一致
• 兼容性：完全覆盖1~1e6的所有输入场景，边界情况（输入1、输入1e6、输入2等）都能正确处理

内容的提问来源于stack exchange，提问作者Will Berner