3536. 两个数字的最大乘积 

English Version

题目描述

给定一个正整数 n。

返回 任意两位数字 相乘所得的最大乘积。

注意：如果某个数字在 n 中出现多次，你可以多次使用该数字。

示例 1：

输入： n = 31

输出： 3

解释：

n 的数字是 [3, 1]。
任意两位数字相乘的结果为：3 * 1 = 3。
最大乘积为 3。

示例 2：

输入： n = 22

输出： 4

解释：

n 的数字是 [2, 2]。
任意两位数字相乘的结果为：2 * 2 = 4。
最大乘积为 4。

示例 3：

输入： n = 124

输出： 8

解释：

n 的数字是 [1, 2, 4]。
任意两位数字相乘的结果为：1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8。
最大乘积为 8。

提示：

10 <= n <= 10⁹

解法

方法一：找到最大和次大数字

我们用两个变量 $a$ 和 $b$ 来记录当前最大的数字和次大的数字。我们遍历 $n$ 的每一位数字，如果当前数字大于 $a$，则将 $b$ 赋值为 $a$，然后将 $a$ 赋值为当前数字；否则，如果当前数字大于 $b$，则将 $b$ 赋值为当前数字。最后返回 $a \times b$ 即可。

时间复杂度 $O(\log n)$，其中 $n$ 是输入数字的大小。空间复杂度 $O(1)$。

Python3

class Solution:
    def maxProduct(self, n: int) -> int:
        a = b = 0
        while n:
            n, x = divmod(n, 10)
            if a < x:
                a, b = x, a
            elif b < x:
                b = x
        return a * b

Java

class Solution {
    public int maxProduct(int n) {
        int a = 0, b = 0;
        for (; n > 0; n /= 10) {
            int x = n % 10;
            if (a < x) {
                b = a;
                a = x;
            } else if (b < x) {
                b = x;
            }
        }
        return a * b;
    }
}

C++

class Solution {
public:
    int maxProduct(int n) {
        int a = 0, b = 0;
        for (; n; n /= 10) {
            int x = n % 10;
            if (a < x) {
                b = a;
                a = x;
            } else if (b < x) {
                b = x;
            }
        }
        return a * b;
    }
};

Go

func maxProduct(n int) int {
	a, b := 0, 0
	for ; n > 0; n /= 10 {
		x := n % 10
		if a < x {
			b, a = a, x
		} else if b < x {
			b = x
		}
	}
	return a * b
}

TypeScript

function maxProduct(n: number): number {
    let [a, b] = [0, 0];
    for (; n; n = Math.floor(n / 10)) {
        const x = n % 10;
        if (a < x) {
            [a, b] = [x, a];
        } else if (b < x) {
            b = x;
        }
    }
    return a * b;
}