2815-数组中的最大数对和

给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。

返回最大和，如果不存在满足题意的数字对，返回 -1 。

示例 1：

**输入：** nums = [51,71,17,24,42]
**输出：** 88
**解释：**
i = 1 和 j = 2 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。 
i = 3 和 j = 4 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。
可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。

示例 2：

**输入：** nums = [1,2,3,4]
**输出：** -1
**解释：** 不存在数对满足数位上最大的数字相等。

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104

请看 视频讲解 。

用一个长为 10 的数组 maxVal}[i] 维护最大数位为 i 的元素的最大值。

当我们遍历到 nums}[i] 时，设其最大数位为 maxD，那么用

\textit{nums}[i] + \textit{maxVal}[\textit{maxD}]

更新答案。

[sol-Python3]

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        ans = -1
        max_val = [-inf] * 10
        for v in nums:
            max_d = max(map(int, str(v)))
            ans = max(ans, v + max_val[max_d])
            max_val[max_d] = max(max_val[max_d], v)
        return ans

[sol-Java]

class Solution {
    public int maxSum(int[] nums) {
        int ans = -1;
        var maxVal = new int[10];
        Arrays.fill(maxVal, Integer.MIN_VALUE);
        for (int v : nums) {
            int maxD = 0;
            for (int x = v; x > 0; x /= 10)
                maxD = Math.max(maxD, x % 10);
            ans = Math.max(ans, v + maxVal[maxD]);
            maxVal[maxD] = Math.max(maxVal[maxD], v);
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int maxSum(vector<int> &nums) {
        int ans = -1;
        vector<int> max_val(10, INT_MIN);
        for (int v: nums) {
            int max_d = 0;
            for (int x = v; x; x /= 10)
                max_d = max(max_d, x % 10);
            ans = max(ans, v + max_val[max_d]);
            max_val[max_d] = max(max_val[max_d], v);
        }
        return ans;
    }
};

[sol-Go]

func maxSum(nums []int) int {
	ans := -1
	maxVal := [10]int{}
	for i := range maxVal {
		maxVal[i] = math.MinInt // 表示不存在最大值
	}
	for _, v := range nums {
		maxD := 0
		for x := v; x > 0; x /= 10 {
			maxD = max(maxD, x%10)
		}
		ans = max(ans, v+maxVal[maxD])
		maxVal[maxD] = max(maxVal[maxD], v)
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }

[sol-JavaScript]

var maxSum = function (nums) {
    let ans = -1;
    let maxVal = Array(10).fill(Number.MIN_SAFE_INTEGER);
    for (const v of nums) {
        let maxD = 0;
        for (let x = v; x; x = Math.floor(x / 10))
            maxD = Math.max(maxD, x % 10);
        ans = Math.max(ans, v + maxVal[maxD]);
        maxVal[maxD] = Math.max(maxVal[maxD], v);
    }
    return ans;
};

复杂度分析

• 时间复杂度：\mathcal{O}(n\log U)，其中 n 为 nums 的长度，U=max(\textit{nums})。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。