Easy

题目描述

给定一个正整数 n。

返回 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^9

提示：

  • 使用暴力法

解题思路

这道题要求找到一个数字中任意两个数位的最大乘积。我们可以有两种主要思路：

方法一：暴力法 提取出数字的所有数位，然后枚举所有可能的两个数位组合，计算它们的乘积并维护最大值。这种方法直观易懂，时间复杂度为 O(d²)，其中 d 是数字的位数。

方法二：排序优化（推荐） 由于我们要找最大乘积，可以先提取所有数位，然后对数位进行排序。最大的乘积一定是最大的两个数位相乘得到的。这样我们只需要找到最大和次大的数位即可。时间复杂度为 O(d log d)，但在实际中由于数位个数很少（最多10位），常数时间很小。

具体实现时，我们可以通过不断对数字取模10来提取每一位数字，将所有数位存储在数组中，然后排序取最大的两个数位相乘。

对于边界情况，题目保证 n >= 10，所以至少有两个数位，不需要额外处理。

代码实现

class Solution {
public:
    int maxProduct(int n) {
        vector<int> digits;
        while (n > 0) {
            digits.push_back(n % 10);
            n /= 10;
        }
        
        sort(digits.rbegin(), digits.rend());
        return digits[0] * digits[1];
    }
};

class Solution:
    def maxProduct(self, n: int) -> int:
        digits = []
        while n > 0:
            digits.append(n % 10)
            n //= 10
        
        digits.sort(reverse=True)
        return digits[0] * digits[1]

public class Solution {
    public int MaxProduct(int n) {
        List<int> digits = new List<int>();
        while (n > 0) {
            digits.Add(n % 10);
            n /= 10;
        }
        
        digits.Sort((a, b) => b.CompareTo(a));
        return digits[0] * digits[1];
    }
}

var maxProduct = function(n) {
    let digits = [];
    while (n > 0) {
        digits.push(n % 10);
        n = Math.floor(n / 10);
    }
    
    digits.sort((a, b) => b - a);
    return digits[0] * digits[1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(d log d)，其中 d 是数字的位数，主要消耗在排序上
空间复杂度O(d)，需要额外数组存储所有数位