给数字单个位数加5求最大值的Java代码时间复杂度优化

你原来的代码时间复杂度是O(d²)（d为输入数字的位数，最多6位），可以优化到O(d)时间复杂度，核心是不用枚举所有加5的可能性，直接定位最优的加5位置即可，判断逻辑如下：

• 给某一位加5后，如果该位原值≥5，加完会变成两位数，整个数字的长度会+1，位数更多的数字一定比位数少的大，所以只要存在≥5的位，优先选最靠右的≥5的位加5，这样高位不会被拆分变小，结果最大
• 如果所有位都<5，加5后不会改变数字长度，选最靠左的位加5，高位提升带来的收益最大

public static int process(int number) {
    // 边界处理：输入为0直接返回5
    if (number == 0) {
        return 5;
    }
    char[] digits = String.valueOf(number).toCharArray();
    int len = digits.length;
    int lastGe5 = -1;
    int firstLess5 = -1;
    // 一次遍历记录需要的位置
    for (int i = 0; i < len; i++) {
        int num = digits[i] - '0';
        if (num < 5 && firstLess5 == -1) {
            firstLess5 = i;
        }
        if (num >= 5) {
            lastGe5 = i;
        }
    }
    StringBuilder sb = new StringBuilder();
    if (lastGe5 != -1) {
        // 存在≥5的位，给最靠右的加5
        for (int i = 0; i < len; i++) {
            if (i == lastGe5) {
                sb.append((digits[i] - '0') + 5);
            } else {
                sb.append(digits[i]);
            }
        }
    } else {
        // 所有位都<5，给最靠左的加5
        for (int i = 0; i < len; i++) {
            if (i == firstLess5) {
                sb.append((digits[i] - '0') + 5);
            } else {
                sb.append(digits[i]);
            }
        }
    }
    return Integer.parseInt(sb.toString());
}

优化效果说明 #

1. 时间复杂度从O(d²)降至O(d)，仅需两次线性遍历（甚至可以合并成一次），没有嵌套循环，执行效率提升明显
2. 逻辑完全覆盖所有测试场景：
   • 输入555：所有位≥5，选最后一位加5得5510，符合示例1
   • 输入444：所有位<5，选第一位加5得944，符合示例2
   • 输入534：仅第一位≥5，加5得1034，是所有可能中的最大值
   • 输入654：最靠右的≥5位是第二位的5，加5得6104，为最大值
3. 完全适配输入范围0~100000的约束，边界情况处理正常

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