Medium

题目描述

给你两个长度为 n 的整数数组 x 和 y。你必须选择三个不同的索引 i、j 和 k，使得：

  • x[i] != x[j]
  • x[j] != x[k]
  • x[k] != x[i]

你的目标是在这些条件下最大化 y[i] + y[j] + y[k] 的值。返回通过选择这样的三元组索引可以获得的最大可能和。

如果不存在这样的三元组，返回 -1。

示例 1：

输入：x = [1,2,1,3,2], y = [5,3,4,6,2]
输出：14
解释：
选择 i = 0（x[i] = 1, y[i] = 5）、j = 1（x[j] = 2, y[j] = 3）、k = 3（x[k] = 3, y[k] = 6）。
从 x 中选择的三个值都不相同。5 + 3 + 6 = 14 是我们能获得的最大值。因此输出是 14。

示例 2：

输入：x = [1,2,1,2], y = [4,5,6,7]
输出：-1
解释：
x 中只有两个不同的值。因此输出是 -1。

约束条件：

  • n == x.length == y.length
  • 3 <= n <= 10^5
  • 1 <= x[i], y[i] <= 10^6

解题思路

这道题要求我们从数组中选择三个不同 x 值对应的 y 值，使其和最大。

核心思路：

  1. 对于相同的 x 值，我们只需要保留对应的最大 y 值，因为选择更大的 y 值总是更优的
  2. 将所有不同的 x 值及其对应的最大 y 值收集起来
  3. 如果不同的 x 值少于 3 个，直接返回 -1
  4. 从所有候选对中选择 y 值最大的三个即可

算法步骤：

  1. 使用哈希表记录每个 x 值对应的最大 y 值
  2. 将所有 (x, max_y) 对提取出来
  3. 按 y 值降序排序，选择前三个 y 值求和

这种方法的正确性在于：由于我们需要三个不同的 x 值，而对于每个 x 值我们只能选择一次，所以贪心地选择每个 x 值对应的最大 y 值，然后从中选择 y 值最大的三个组合即可获得最优解。

时间复杂度主要来自排序操作。

代码实现

class Solution {
public:
    int maxSumDistinctTriplet(vector<int>& x, vector<int>& y) {
        unordered_map<int, int> maxY;
        
        // 对每个x值保留最大的y值
        for (int i = 0; i < x.size(); i++) {
            maxY[x[i]] = max(maxY[x[i]], y[i]);
        }
        
        // 如果不同的x值少于3个，返回-1
        if (maxY.size() < 3) {
            return -1;
        }
        
        // 提取所有y值并排序
        vector<int> yValues;
        for (auto& pair : maxY) {
            yValues.push_back(pair.second);
        }
        
        sort(yValues.rbegin(), yValues.rend());
        
        return yValues[0] + yValues[1] + yValues[2];
    }
};

class Solution:
    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
        max_y = {}
        
        # 对每个x值保留最大的y值
        for i in range(len(x)):
            max_y[x[i]] = max(max_y.get(x[i], 0), y[i])
        
        # 如果不同的x值少于3个，返回-1
        if len(max_y) < 3:
            return -1
        
        # 提取所有y值并排序
        y_values = list(max_y.values())
        y_values.sort(reverse=True)
        
        return y_values[0] + y_values[1] + y_values[2]

public class Solution {
    public int MaxSumDistinctTriplet(int[] x, int[] y) {
        Dictionary<int, int> maxY = new Dictionary<int, int>();
        
        // 对每个x值保留最大的y值
        for (int i = 0; i < x.Length; i++) {
            if (maxY.ContainsKey(x[i])) {
                maxY[x[i]] = Math.Max(maxY[x[i]], y[i]);
            } else {
                maxY[x[i]] = y[i];
            }
        }
        
        // 如果不同的x值少于3个，返回-1
        if (maxY.Count < 3) {
            return -1;
        }
        
        // 提取所有y值并排序
        List<int> yValues = new List<int>(maxY.Values);
        yValues.Sort((a, b) => b.CompareTo(a));
        
        return yValues[0] + yValues[1] + yValues[2];
    }
}

var maxSumDistinctTriplet = function(x, y) {
    const maxY = new Map();
    
    // 对每个x值保留最大的y值
    for (let i = 0; i < x.length; i++) {
        maxY.set(x[i], Math.max(maxY.get(x[i]) || 0, y[i]));
    }
    
    // 如果不同的x值少于3个，返回-1
    if (maxY.size < 3) {
        return -1;
    }
    
    // 提取所有y值并排序
    const yValues = Array.from(maxY.values());
    yValues.sort((a, b) => b - a);
    
    return yValues[0] + yValues[1] + yValues[2];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O(n log k)，其中 n 是数组长度，k 是不同 x 值的个数，主要消耗在排序上
空间复杂度O(k)，用于存储哈希表和 y 值数组，其中 k 是不同 x 值的个数

相关题目