跳转至

3536. 两个数字的最大乘积

题目描述

给定一个正整数 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 <= 109

解法

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
}

评论