题目描述

给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。

如果无法得到答案，请返回一个空字符串。

样例

输入：digits = [8,1,9]
输出："981"

输入：digits = [8,6,7,1,0]
输出："8760"

输入：digits = [1]
输出：""

输入：digits = [0,0,0,0,0,0]
输出："0"

限制

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9
• 返回的结果不应包含不必要的前导零。

算法

(暴力枚举，数学) $O(n)$

1. 求出所有数字模 3 的和，然后求出最小的两个模 3 等于 1 的数字 x1 和 y1，以及最小的两个模 3 等于 2 的数字 x2 和 y2（不存在则记为 10）。
2. 如果所有数字的和模 3 等于 0，则按从大到小的顺序拼接数字作为答案。
3. 如果所有数字的和模 3 等于 1，则尝试删掉一个 x1 ，如果不存在，则尝试删掉 x2 和 y2。其余的数字从大到小拼接作为答案。
4. 如果所有数字的和模 3 等于 2，则尝试删掉一个 x2 ，如果不存在，则尝试删掉 x1 和 y1。其余的数字从大到小拼接作为答案。

时间复杂度

• 每个数字仅遍历常数次，则时间复杂度为 $O(n)$。

空间复杂度

• 答案需要额外 $O(n)$ 的空间。

C++ 代码

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        int n = digits.size();

        sort(digits.begin(), digits.end());

        int sum = 0, x1 = 10, y1 = 10, x2 = 10, y2 = 10;
        for (int i = 0; i < n; i++) {
            sum += digits[i] % 3;
            if (digits[i] % 3 == 1) {
                if (x1 > digits[i]) {
                    y1 = x1;
                    x1 = digits[i];
                } else if (y1 > digits[i]) {
                    y1 = digits[i];
                }
            } else if (digits[i] % 3 == 2) {
                if (x2 > digits[i]) {
                    y2 = x2;
                    x2 = digits[i];
                } else if (y2 > digits[i]) {
                    y2 = digits[i];
                }
            }
        }

        string ans;
        if (sum % 3 == 0) {
            for (int i = 0; i < n; i++)
                ans += to_string(digits[i]);
        } else if (sum % 3 == 1) {
            if (x1 < 10) {
                for (int i = 0; i < n; i++) {
                    if (digits[i] == x1) {
                        x1 = 10;
                        continue;
                    }
                    ans += to_string(digits[i]);
                }
            } else if (x2 < 10 && y2 < 10) {
                for (int i = 0; i < n; i++) {
                    if (digits[i] == x2) {
                        x2 = 10;
                        continue;
                    } else if (digits[i] == y2) {
                        y2 = 10;
                        continue;
                    }
                    ans += to_string(digits[i]);
                }
            }
        } else {
            if (x2 < 10) {
                for (int i = 0; i < n; i++) {
                    if (digits[i] == x2) {
                        x2 = 10;
                        continue;
                    }
                    ans += to_string(digits[i]);
                }
            } else if (x1 < 10 && y1 < 10) {
                for (int i = 0; i < n; i++) {
                    if (digits[i] == x1) {
                        x1 = 10;
                        continue;
                    } else if (digits[i] == y1) {
                        y1 = 10;
                        continue;
                    }
                    ans += to_string(digits[i]);
                }
            }
        }

        while (ans.length() > 1 && ans.back() == '0')
            ans.pop_back();

        reverse(ans.begin(), ans.end());

        return ans;
    }
};