数组中的最大数对和-LeetCode

2815.数组中的最大数对和

🎯 问题描述

描述：
给定一个整数数组 nums，找出两个下标 i 和 j（i < j），使得 nums[i] 和 nums[j] 的最大数位相同，并且 nums[i] + nums[j] 的值最大。
如果不存在这样的数对，返回 -1。

说明：

• 这是对“数位和”问题的变体。

• 分组依据从“数位之和”变成了“数位最大值”。

• 例如：129 的最大数位是 9，901 的最大数位也是 9，它们可以配对。

• 示例：

• 示例 1：

输入：nums = [129, 901, 55, 34]
输出：1030
解释：
- 129 的最大数位是 9。
- 901 的最大数位是 9。
- 它们可以配对，和为 129 + 901 = 1030。
- 55 的最大数位是 5，没有其他数最大数位是 5。
- 34 的最大数位是 4，没有其他数最大数位是 4。

💻 解题思路

思路1：哈希表 + 贪心

思路1：代码实现

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        # 哈希表：键为最大数位，值为该组中最大的数字
        count = defaultdict(int)
        ans = -1
        
        for num in nums:
            # 计算当前数字的最大数位
            pre = int(max(str(num)))
            
            # 如果该最大数位之前出现过
            if pre in count:
                # 1. 尝试更新最大和：当前数字 + 历史该组最大数字
                ans = max(ans, num + count[pre])
                
                # 2. 维护左（更新历史最大值）：
                # 贪心策略：保留该组中最大的数字，以便后续配对获得更大的和
                count[pre] = max(num, count[pre])
            else:
                # 第一次出现该最大数位，直接存入
                count[pre] = num
                
        return ans

思路1：📊 性能分析

• 时间复杂度：$O(N \times \log M)$
  • 其中 $N$ 是数组长度，$M$ 是数字的最大值。
  • 计算 max(str(num)) 需要遍历数字的每一位，耗时 $O(\log_{10} M)$。
  • 总时间复杂度为 $O(N \log M)$。
• 空间复杂度：$O(1)$
  • 哈希表的键是 0-9 的整数，最多只有 10 个键。
  • 因此空间复杂度是常数级的。

思考

1. 分组依据的变化：

   • 之前的题目是按“数位和”分组，这里是按“最大数位”分组。
   • 逻辑完全一致：只要分组键相同，就可以配对。

2. “枚举右，维护左”的体现：

   • 枚举右：遍历当前的 num。
   • 维护左：count[pre] 存储了左边（历史）所有最大数位为 pre 的数字中的最大值。
   • 我们不需要存储所有历史数字，只需要存储最大的那个，因为我们要最大化 num + history。

3. 边界情况：

   • 单个数字：无法配对，返回 -1。
   • 所有数字最大数位都不同：返回 -1。
   • 负数处理：题目通常假设为正整数。如果有负数，max(str(-12)) 会变成 max(['-', '1', '2'])，结果是 '2'（字符比较），逻辑可能会出错。如果是正整数数组，该代码完全正确。