Medium

题目描述

给你一个整数数组 nums。

你的任务是找到两个不同的下标 i 和 j，使得乘积 nums[i] * nums[j] 最大化，且 nums[i] 和 nums[j] 的二进制表示没有任何公共的置位位。

返回这样一对数的最大可能乘积。如果不存在这样的一对，返回 0。

示例 1：

输入：nums = [1,2,3,4,5,6,7]
输出：12
解释：
最佳一对是 3 (011) 和 4 (100)。它们没有共享置位位，且 3 * 4 = 12。

示例 2：

输入：nums = [5,6,4]
输出：0
解释：
每一对数字都至少有一个公共的置位位。因此，答案是 0。

示例 3：

输入：nums = [64,8,32]
输出：2048
解释：
没有一对数字共享公共位，所以答案是两个最大元素的乘积，64 和 32 (64 * 32 = 2048)。

约束条件：

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

解题思路

这道题的关键是高效地找到没有公共位的数对。直接的暴力方法是 O(n²)，对于大数据会超时。

核心思路：

  1. 将每个数看作位掩码，两个数没有公共位等价于它们的按位与为 0
  2. 使用动态规划优化查找过程，构建一个 dp 数组存储每个位掩码对应的最大值
  3. 对于每个数 x，计算其补集掩码，在补集的所有子集中找最大值与 x 相乘

算法步骤：

  1. 确定位宽 B（这里取 20 位足够覆盖 10^6）
  2. 初始化 dp 数组，dp[mask] 表示恰好等于该掩码的数中的最大值
  3. 使用子集枚举技巧，将每个掩码的值传播到其所有超集
  4. 对于每个数 x，计算补集掩码 (~x) & ((1«B)-1)，查询 dp[补集] 得到最佳搭档
  5. 维护全局最大乘积

这种方法将复杂度从 O(n²) 优化到 O(n + 2^B)，其中 B=20，大大提升了效率。

代码实现

class Solution {
public:
    long long maxProduct(vector<int>& nums) {
        const int B = 20;
        vector<int> dp(1 << B, 0);
        
        // 初始化dp数组
        for (int num : nums) {
            dp[num] = max(dp[num], num);
        }
        
        // 传播到超集
        for (int mask = 0; mask < (1 << B); mask++) {
            if (dp[mask] == 0) continue;
            for (int bit = 0; bit < B; bit++) {
                if (!(mask & (1 << bit))) {
                    int supermask = mask | (1 << bit);
                    dp[supermask] = max(dp[supermask], dp[mask]);
                }
            }
        }
        
        long long result = 0;
        for (int num : nums) {
            int complement = (~num) & ((1 << B) - 1);
            if (dp[complement] > 0) {
                result = max(result, (long long)num * dp[complement]);
            }
        }
        
        return result;
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        B = 20
        dp = [0] * (1 << B)
        
        # 初始化dp数组
        for num in nums:
            dp[num] = max(dp[num], num)
        
        # 传播到超集
        for mask in range(1 << B):
            if dp[mask] == 0:
                continue
            for bit in range(B):
                if not (mask & (1 << bit)):
                    supermask = mask | (1 << bit)
                    dp[supermask] = max(dp[supermask], dp[mask])
        
        result = 0
        for num in nums:
            complement = (~num) & ((1 << B) - 1)
            if dp[complement] > 0:
                result = max(result, num * dp[complement])
        
        return result

public class Solution {
    public long MaxProduct(int[] nums) {
        const int B = 20;
        int[] dp = new int[1 << B];
        
        // 初始化dp数组
        foreach (int num in nums) {
            dp[num] = Math.Max(dp[num], num);
        }
        
        // 传播到超集
        for (int mask = 0; mask < (1 << B); mask++) {
            if (dp[mask] == 0) continue;
            for (int bit = 0; bit < B; bit++) {
                if ((mask & (1 << bit)) == 0) {
                    int supermask = mask | (1 << bit);
                    dp[supermask] = Math.Max(dp[supermask], dp[mask]);
                }
            }
        }
        
        long result = 0;
        foreach (int num in nums) {
            int complement = (~num) & ((1 << B) - 1);
            if (dp[complement] > 0) {
                result = Math.Max(result, (long)num * dp[complement]);
            }
        }
        
        return result;
    }
}

var maxProduct = function(nums) {
    const B = 20;
    const dp = new Array(1 << B).fill(0);
    
    // 初始化dp数组
    for (const num of nums) {
        dp[num] = Math.max(dp[num], num);
    }
    
    // 传播到超集
    for (let mask = 0; mask < (1 << B); mask++) {
        if (dp[mask]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + 2^B × B)其中 n 是数组长度，B=20，初始化 O(n)，传播 O(2^B × B)，查询 O(n)
空间复杂度O(2^B)dp 数组大小为 2^20

相关题目