What is the main pattern used in Maximize Y-Sum by Picking a Triplet of Distinct X-Values?

The core pattern is array scanning combined with hash lookup to track the maximum y for each unique x.

How do I handle duplicates in x while maximizing the y-sum?

Keep only the maximum y for each unique x in a hash map and ignore smaller y-values for the same x.

What should I return if fewer than three distinct x-values exist?

Return -1 because no valid triplet can be formed.

Is sorting all y-values necessary for this problem?

No, only the maximum y-values for each unique x need to be sorted, reducing unnecessary computation.

Can this approach scale to large arrays?

Yes, using a hash map to track maximum y-values ensures O(n) preprocessing and O(k log k) sorting, suitable for n up to 105.

#3572

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

选择不同 X 值三元组使 Y 值之和最大

给你两个整数数组 x 和 y ，长度均为 n 。你必须选择三个不同的下标 i ， j 和 k ，满足以下条件： x[i] != x[j] x[j] != x[k] x[k] != x[i] 你的目标是在满足这些条件下最大化 y[i] + y[j] + y[k] 的值。返回通过选择这样一组三元组…

数组哈希表贪心排序堆（优先队列）

题目描述

给你两个整数数组 x 和 y，长度均为 n。你必须选择三个不同的下标 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⁵
1 <= x[i], y[i] <= 10⁶

lightbulb

解题思路

方法一：排序 + 贪心 + 哈希表

我们将数组 $x$ 和 $y$ 中的元素配对成一个二维数组 $\textit{arr}$ ，然后按照 $y$ 的值从大到小对 $\textit{arr}$ 进行排序。接下来，我们使用一个哈希表来记录已经选择的 $x$ 值，并遍历 $\textit{arr}$ ，每次选择一个未被选择的 $x$ 值和对应的 $y$ 值，直到选择了三个不同的 $x$ 值为止。

如果在遍历过程中选择了三个不同的 $x$ 值，则返回这三个 $y$ 值的和；如果遍历结束后仍未选择三个不同的 $x$ 值，则返回 -1。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{x}$ 和 $\textit{y}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
        arr = [(a, b) for a, b in zip(x, y)]
        arr.sort(key=lambda x: -x[1])
        vis = set()
        ans = 0
        for a, b in arr:
            if a in vis:
                continue
            vis.add(a)
            ans += b
            if len(vis) == 3:
                return ans
        return -1

speed

复杂度分析

指标	值
时间	complexity is O(n) for building the hash map and O(k log k) for sorting k unique x-values, where k <= n. Space complexity is O(k) for storing maximum y-values for each unique x in the hash map.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask for maximum sum with distinct x-values
question_mark
Check if candidate ignores duplicate x-values when selecting y
question_mark
Look for O(n) hash map preprocessing plus sorting for top three selection

warning

常见陷阱

外企场景

error
Including multiple y-values for the same x, leading to invalid triplets
error
Not handling fewer than three unique x-values, returning incorrect sum
error
Sorting all y-values instead of only the maximums, increasing unnecessary computation

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize sum with four distinct x-values instead of three
arrow_right_alt
Select triplet under a threshold constraint on y-values
arrow_right_alt
Minimize sum by picking distinct x-values instead of maximizing

help

常见问题

外企场景

继续练习

#2813 子序列最大优雅度 #3462 提取至多 K 个元素的最大总和 #3362 零数组变换 III