What is the main pattern used in Largest Multiple of Three?

The primary pattern is state transition dynamic programming, applied to digit groups modulo three to select removals optimally.

Can the input array contain zeros only?

Yes, but the largest multiple of three in that case is simply "0" without additional digits or leading zeros.

How do I handle single-digit arrays that are not multiples of three?

Return an empty string since no combination can form a multiple of three.

Is sorting necessary in this solution?

Yes, sorting the remaining digits in descending order ensures the largest number is formed after state transitions.

Why does GhostInterview emphasize remainder classification?

Classifying digits by remainder modulo three allows efficient state transitions to remove minimal digits and maximize the final multiple of three.

#1363

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

形成三的最大倍数

给你一个整数数组 digits ，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。如果无法得到答案，请返回一个空字符串。返回的结果不应包含不必要的前导零。示例 1：输入： digits…

数组数学动态规划贪心排序

题目描述

给你一个整数数组 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^4
0 <= digits[i] <= 9

lightbulb

解题思路

方法一：贪心 + 动态规划 + 逆推

我们定义 $f[i][j]$ 表示在前 $i$ 个数中选取若干个数，使得选取的数的和模 $3$ 为 $j$ 的最大长度。为了使得选取的数最大，我们需要尽可能选取更多的数，因此我们需要使得 $f[i][j]$ 尽可能大。我们初始化 $f[0][0] = 0$ ，其余的 $f[0][j] = -\infty$ 。

考虑 $f[i][j]$ 如何进行状态转移。我们可以不选取第 $i$ 个数，此时 $f[i][j] = f[i - 1][j]$ ；我们也可以选取第 $i$ 个数，此时 $f[i][j] = f[i - 1][(j - x_i \bmod 3 + 3) \bmod 3] + 1$ ，其中 $x_i$ 表示第 $i$ 个数的值。因此我们有如下的状态转移方程：

f[i][j] = \max \{ f[i - 1][j], f[i - 1][(j - x_i \bmod 3 + 3) \bmod 3] + 1 \}

如果 $f[n][0] \le 0$ ，那么我们无法选取任何数，因此答案字符串为空。否则我们可以通过 $f$ 数组进行逆推，找出选取的数。

定义 $i = n$ , $j = 0$ ，从 $f[i][j]$ 开始逆推，记 $k = (j - x_i \bmod 3 + 3) \bmod 3$ ，如果 $f[i - 1][k] + 1 = f[i][j]$ ，那么我们选取了第 $i$ 个数，否则我们没有选取第 $i$ 个数。如果我们选取了第 $i$ 个数，那么我们将 $j$ 更新为 $k$ ，否则我们保持 $j$ 不变。为了使得同等长度的数最大，我们应该优先选取较大的数，因此，我们在前面首先对数组进行排序。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort()
        n = len(digits)
        f = [[-inf] * 3 for _ in range(n + 1)]
        f[0][0] = 0
        for i, x in enumerate(digits, 1):
            for j in range(3):
                f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + 1)
        if f[n][0] <= 0:
            return ""
        arr = []
        j = 0
        for i in range(n, 0, -1):
            k = (j - digits[i - 1] % 3 + 3) % 3
            if f[i - 1][k] + 1 == f[i][j]:
                arr.append(digits[i - 1])
                j = k
        i = 0
        while i < len(arr) - 1 and arr[i] == 0:
            i += 1
        return "".join(map(str, arr[i:]))

speed

复杂度分析

指标	值
时间	complexity is O(n + k log k) where n is the number of digits and k is the remaining digits after removal, mainly due to sorting. Space complexity is O(n) for storing grouped digits and intermediate states required by the state transition dynamic programming approach.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the sum of digits modulo three is zero to quickly identify multiples of three.
question_mark
Consider edge cases with many zeros or a single digit that cannot form a multiple of three.
question_mark
Verify your state transitions correctly remove minimal digits to maximize the final number.

warning

常见陷阱

外企场景

error
Failing to remove the smallest number of digits needed, resulting in suboptimal output.
error
Leaving unnecessary leading zeros in the final string.
error
Ignoring digits classification by modulo three, which breaks the dynamic programming logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the smallest multiple of three instead of the largest, adjusting sorting strategy.
arrow_right_alt
Return the largest multiple of five from digits using similar state transition reasoning.
arrow_right_alt
Compute the largest multiple of k for any k using remainder-based dynamic programming extensions.

help

常见问题

外企场景

继续练习

#1262 可被三整除的最大和 #1648 销售价值减少的颜色球 #646 最长数对链