题目大意：
形成三的最大倍数
给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。
由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。
如果无法得到答案，请返回一个空字符串。
示例 1：
输入：digits = [8,1,9] 输出："981"
示例 2：
输入：digits = [8,6,7,1,0] 输出："8760"
示例 3：
输入：digits = [1] 输出：""
示例 4：
输入：digits = [0,0,0,0,0,0] 输出："0"
提示：
1 <= digits.length <= 10^40 <= digits[i] <= 9- 返回的结果不应包含不必要的前导零。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1363
解题思路分析：
首先我们应该明确一个数学上的概念，如果一个数字能被三整除，那么该数字上每一位之和也能被三整除，比如183能被3整除（183/3=61），那么1+8+3=12，12也能被三整除。
我们先循环遍历一遍数组中的数字，该循环中我们需要做4件事情：
- 统计出0-9每种数字的个数
- 计算出数组中所有数字和
- 统计出与三相除余数为1的最小数min1_1，及次小数 min1_2。
- 统计出与三相除余数为2的最小数min2_1，及次小数 min2_2。
循环结束后，如果所有数字和能被3整除，说明我们使用数组中所有的数字可以组成一个能被3整除的数字。如果和与3的余数是1，说明我们需要从数组中剔除出一个最小的与3余数是1的数字 min1_1 。如果这个数字不存在，那么数组中一定存在 min2_1 和 min2_2，将这两个数字在数组中的个数减一。反之，如果和与3的余数是2，说明我们需要从数组中剔除出一个最小的与3余数是2的数字min2_1 。如果这个数字不存在，那么数组中一定存在 min1_1 和 min1_2，将这两个数字在数组中的个数减一。
经过上述操作，我们保证数组中剩下的数字和一定能被三整除，我们利用这些数字组成一个最大数即可（最大数即是将大的数字尽量放在高位）。
实现代码：
public String largestMultipleOfThree(int[] digits) {
// 统计每种数字出现的次数
int[] count = new int[10];
// 所有数字和
int sum=0;
// 除以3余数为1的最小数及次小数
// 除以3余数为2的最小数及次小数
int min1_1=10,min1_2=10,min2_1=10,min2_2=10;
// 循环每个数字
for(int d : digits){
// 当前数字与3的余数为1
if(d%3==1){
// 更新余数为1的最小数及次小数
if(d<=min1_1){
min1_2=min1_1;
min1_1=d;
}else if(d<=min1_2){
min1_2=d;
}
}
// 当前数字与3的余数为2
else if(d%3==2){
// 更新余数为2的最小数及次小数
if(d<=min2_1){
min2_2=min2_1;
min2_1=d;
}else if(d<=min2_2){
min2_2=d;
}
}
// 累加数字和
sum+=d;
// 当前数字个数加一
count[d]++;
}
// 如果和是0，直接返回0
if(sum==0) return "0";
// 如果和与3的余数是1
if(sum%3==1){
// 如果存在min1_1，min1_1的个数减一
if(min1_1<10) count[min1_1]--;
else{
// 否则减去两个最小的余数为2的数
count[min2_1]--;
count[min2_2]--;
}
}else if(sum%3==2){
if(min2_1<10) count[min2_1]--;
else{
count[min1_1]--;
count[min1_2]--;
}
}
// 构建最大数
StringBuilder sb = new StringBuilder();
for(int i=9;i>=0;i--){
for(int j=0;j<count[i];j++){
sb.append(i);
}
}
return sb.toString();
}本题解法执行时间为3ms。
Runtime: 3 ms, faster than 81.62% of Java online submissions for Largest Multiple of Three.
Memory Usage: 41.6 MB, less than 100.00% of Java online submissions for Largest Multiple of Three.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1363-largest-multiple-of-three-解题思路分析/