LeetCode 1363. 形成三的最大倍数

2021-12-10 HGNULB 约 11 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 1363. 形成三的最大倍数

题意分析

给一堆 0 到 9 的数字，可以任意挑选其中一部分并任意排列，拼成一个能被 3 整除的整数，要求这个整数尽可能大。拼不出来就返回空串。

「可以任意排列」这句话把顺序问题彻底消解掉了：既然位置随便排，那么选定一个数字多重集之后，最大的排法必然是从大到小排列，不需要任何决策。真正要决定的只有「保留哪些数字」。

「大」的比较规则要拆成两层：位数多的一定更大，所以第一优先是让保留的数字尽可能多；位数相同时才逐位比较，此时要让高位尽可能大，等价于在删同样多个数字的前提下删掉最小的那些。

两个必须单独处理的输出边界：一是所有数字都被删光，返回空串而不是 "0"；二是结果全是 0（比如输入是一串 0），此时首字符为 0，必须压成单个 "0"，不能输出 "000" 这种带前导零的形式。

数字总数可达 $10^4$，但取值只有十种，天然适合用长度为 10 的计数数组代替排序。

解法：计数 + 贪心

核心思路

暴力做法是枚举所有子集判断和能否被 3 整除，规模 $2^n$，$n$ 上万时毫无可能。稍好一点的是背包型 DP：按余数分三档记录「取到第 $i$ 个数字、当前和模 3 为 $r$」时的最优结果，但状态里要存字符串，比较和拷贝的开销也不小。

突破口是整除 3 的判定法则：一个数能被 3 整除当且仅当它的各位数字之和能被 3 整除。而数字和与排列顺序无关，于是整个问题被压缩成一句话——从多重集里删掉若干数字，使剩余总和模 3 为 0，并且删得尽量少、删掉的尽量小。

设原始总和为 $S$，$r = S \bmod 3$。$r = 0$ 时一个都不用删。$r = 1$ 时，要把和的余数降 1，只有两种最小代价的做法：删掉一个「模 3 余 1」的数字（即 1、4、7 之一），或者删掉两个「模 3 余 2」的数字（$2 + 2 = 4 \equiv 1$）。$r = 2$ 时两者对调。删三个及以上永远不划算，因为删三个同类余数的数字等价于删一个，位数白白少了两位。

由此得到贪心规则，也是本题的不变量：在所有余数合法的保留方案中，先按保留个数从多到少排序，个数相同时按删掉的数字从小到大排序，取第一个即为最优。落到操作上就是——优先尝试「删一个」，只有当那一类数字一个都没有时才退而求其次「删两个」；每次删除都从该类里最小的数字开始删（1、4、7 的顺序，或 2、5、8 的顺序）。

删同类中最小的为什么最优？因为剩下的数字最终按降序排列，删掉一个较小的数字只会让高位保持不变、低位换成更大的值，绝不会让结果变小。而「宁可删一个大的也不删两个小的」同样成立，因为少一位造成的损失总是压过任何单位数字上的差距。

最后一步是拼接：从 9 到 0 依次按剩余次数输出，天然得到降序排列，不需要真的排序。

解题步骤

一趟遍历，把每个数字计入长度为 10 的 count 数组，同时累加 sum。用计数数组而不是排序，是因为值域只有十个，计数后天然有序。

算 mod = sum % 3。它决定了删除方案，等于 0 时直接跳到拼接阶段，一个数字都不动。

mod == 1 时先调 removeDigits(count, {1,4,7}, 1)，返回假（说明这三种数字一个都没有）才退而调用 removeDigits(count, {2,5,8}, 2)。候选数组按升序列出，保证删除从最小的开始。

mod == 2 时对称处理：先试着删一个余 2 的，失败再删两个余 1 的。

removeDigits 分两阶段：先只做计数不改动，检查这三类数字的总量够不够 need 个；确认够了再真正执行扣减。先验后改是为了避免「删了一半发现不够」而留下被破坏的计数数组——注意 mod == 1 且余 1 的数字不存在时，第一次调用必须干干净净地失败，否则第二套方案就跑在脏数据上了。

拼接阶段从 d = 9 递减到 0，把每个数字按 count[d] 次追加。降序输出直接给出该多重集的最大排列。

收尾判两件事：缓冲区为空返回 ""；首字符是 '0' 说明剩下的全是 0，返回 "0" 以去掉前导零。

以 digits = [8,6,7,1,0] 走一遍：统计得 count[0] = count[1] = count[6] = count[7] = count[8] = 1，sum = 8 + 6 + 7 + 1 + 0 = 22，mod = 22 % 3 = 1。进入 removeDigits(count, {1,4,7}, 1)：检查阶段 remain = 1，看数字 1 有 1 个，remain 归 0，数字 4、7 不再需要，remain == 0 说明可行；执行阶段从最小的 1 开始扣，count[1] 变 0，need 归 0，返回真，因此第二套方案不会被触发。拼接阶段从 9 往下：9 没有，8 输出一次得 "8"，7 输出一次得 "87"，6 得 "876"，5 到 1 都为 0 跳过，0 输出一次得 "8760"。缓冲区非空且首字符是 '8'，直接返回 "8760"。验算 $8+7+6+0 = 21$ 确实是 3 的倍数，而保留四位已是上限——原本五个数字总和余 1，至少要删一个。

再看两个边界：digits = [1] 时 sum = 1、mod = 1，删掉唯一的 1 之后缓冲区为空，返回 ""；digits = [0,0,0,0,0,0] 时 sum = 0、mod = 0，一个不删，拼出 "000000"，首字符是 '0'，压成 "0"。

代码实现

class Solution {
    // 为了让最终数字最大，应尽量少删数字。
    public String largestMultipleOfThree(int[] digits) {
        int[] count = new int[10];
        int sum = 0;
        for (int d : digits) {
            count[d]++;
            sum += d;
        }

        int mod = sum % 3;
        if (mod == 1 && !removeDigits(count, new int[]{1, 4, 7}, 1)) {
            removeDigits(count, new int[]{2, 5, 8}, 2);
        } else if (mod == 2 && !removeDigits(count, new int[]{2, 5, 8}, 1)) {
            removeDigits(count, new int[]{1, 4, 7}, 2);
        }

        StringBuilder res = new StringBuilder();
        for (int d = 9; d >= 0; d--) {
            for (int i = 0; i < count[d]; i++) {
                res.append(d);
            }
        }

        if (res.length() == 0) {
            return "";
        }
        if (res.charAt(0) == '0') {
            return "0";
        }

        return res.toString();
    }

    private boolean removeDigits(int[] count, int[] candidates, int need) {
        int remain = need;
        for (int d : candidates) {
            remain -= Math.min(count[d], remain);
        }

        if (remain > 0) {
            return false;
        }

        for (int d : candidates) {
            while (count[d] > 0 && need > 0) {
                count[d]--;
                need--;
            }
        }

        return true;
    }
}

func largestMultipleOfThree(digits []int) string {
    // 为了让最终数字最大，应尽量少删数字。
    count := make([]int, 10)
    sum := 0
    for _, d := range digits {
        count[d]++
        sum += d
    }

    mod := sum % 3
    if mod == 1 && !removeDigits(count, []int{1, 4, 7}, 1) {
        removeDigits(count, []int{2, 5, 8}, 2)
    } else if mod == 2 && !removeDigits(count, []int{2, 5, 8}, 1) {
        removeDigits(count, []int{1, 4, 7}, 2)
    }

    res := make([]byte, 0, len(digits))
    for d := 9; d >= 0; d-- {
        for i := 0; i < count[d]; i++ {
            res = append(res, byte('0'+d))
        }
    }

    if len(res) == 0 {
        return ""
    }
    if res[0] == '0' {
        return "0"
    }

    return string(res)
}

func removeDigits(count []int, candidates []int, need int) bool {
    remain := need
    for _, d := range candidates {
        if count[d] < remain {
            remain -= count[d]
        } else {
            remain = 0
        }
    }

    if remain > 0 {
        return false
    }

    for _, d := range candidates {
        for count[d] > 0 && need > 0 {
            count[d]--
            need--
        }
    }

    return true
}

复杂度分析

时间复杂度：$O(n)$，统计计数和求和是一趟线性扫描；删除决策只在常数个候选上操作；拼接阶段的总输出长度不超过 $n$。

空间复杂度：$O(1)$ 的辅助空间，只有长度为 10 的计数数组和几个标量；返回的字符串属于必要输出，长度为 $O(n)$。

关键点总结

遇到「整除 3 或 9」的判定，第一反应应当是转成数位和；这一步把排列问题彻底降维成「选哪些数字」的计数问题。

目标是最大数时，比较规则天然分层：先比位数，位数相同再比高位。翻译成贪心就是「删得越少越好，删同样多时删小的」，两层顺序不能颠倒。

「删一个余 1」与「删两个余 2」是同一个余数目标下的两套方案，前者代价严格更小，只有在前者不可行时才回退；删三个同类永远劣于删零个。

值域只有十种时，计数数组既是统计工具也是排序工具，从 9 倒着输出就是降序，省掉了 $O(n \log n)$。

试探型操作要「先验证再执行」，否则失败的那一半改动会污染后续方案。这是本题最容易埋雷的实现细节。

面试视角：这题挂着困难标签，但难点全在分类讨论的完备性——余数两种、每种两套方案、外加空串与全零两个输出边界，一共六个分支。面试时先把这六种情况在纸上列全再动手，比边写边补要稳得多；面试官也常追问「为什么不用 DP」，答案是数位和的性质已经让贪心可证，DP 属于杀鸡用牛刀。

易错点总结

错误写法：余数为 1 时直接去删两个余 2 的数字，不先试删一个余 1 的：digits = [8,6,7,1,0] → 这里余 2 的数字只有 8 一个，凑不够两个，删除动作落空，sum 仍是 22，输出的 "87610" 根本不能被 3 整除；正确做法是删掉那个余 1 的 1，得到 "8760"。

错误写法：删除时从候选里最大的开始删，比如按 7、4、1 的顺序：digits = [1,4,7,7]，sum = 19、mod = 1 → 删掉 7 得到 "741"，而删掉 1 得到 "774"，后者更大。

错误写法：贪心时优先考虑「删掉的数字最小」而不是「删掉的个数最少」：某些输入下删两个 2 比删一个 7 更「便宜」，但位数少了一位，结果必然更小；两层比较的优先级不能反。

错误写法：removeDigits 边检查边扣减，不够时中途返回假 → 第一套方案失败时已经删掉了一部分数字，第二套方案在被破坏的计数上运行，输出的数字凭空少了几位。

错误写法：忘记「结果全为 0」的压缩：digits = [0,0,0,0,0,0] → 输出 "000000"，而正确答案是 "0"。

错误写法：把空结果也返回成 "0"：digits = [1] → 删掉唯一的 1 后什么都不剩，应返回空串，返回 "0" 是错的，因为原输入里根本没有 0 可用。

错误写法：拼接时从 0 循环到 9，得到升序排列 → digits = [8,1,9] 会输出 "189" 而不是最大的 "981"。

错误写法：先对 digits 排序再逐个删除，删除时用 List.remove(Object) 之类按值删除 → 逻辑上可行但复杂度升到 $O(n \log n)$ 甚至 $O(n^2)$，而且相同数字多份时容易删错位置。

错误写法：sum 用 int 却担心溢出而提前取模，导致后面判断 mod 时又取了一次模 → 本题 $n \le 10^4$、每位不超过 9，和最大 $9 \times 10^4$，完全不会溢出，多余的取模只会让代码更容易写错。

错误写法：认为「删两个」时两个数字必须相同 → 删的是两个同余数类的数字，比如一个 2 和一个 5 也满足 $2 + 5 = 7 \equiv 1 \pmod 3$，限制成必须相同会漏掉可行方案。

相似题目

题目	难度	考察点
402. 移掉 K 位数字	中等	顺序固定不可重排，改用单调栈维持字典序最小
179. 最大数	中等	拼接顺序由自定义比较器 `a + b` 与 `b + a` 的大小决定
738. 单调递增的数字	中等	从高位找到第一个下降处后借位，并把后缀全部置 9
670. 最大交换	中等	只准交换一次，需要预处理每个位置右侧最大数字的位置
316. 去除重复字母	中等	每个字符恰好保留一次，栈内弹出还要看后面是否仍有该字符
1449. 数位成本和为目标值的最大数字	困难	预算固定，需先用完全背包求最大位数再贪心还原每一位