Salesforce 三数最大乘积：为何要同时跟踪两个最小值

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 从整数数组选三个不同下标的值相乘，返回数值最大乘积；允许重复数值、负数与零。少于三项在训练代码中抛 ValueError。
• Python 整数不会发生固定宽度溢出；若面试语言是 Java/JS/C++，要先确认整数宽度和乘法溢出策略。
• 题目要求 O(N) 时间，可以用常数个极值变量；不必返回选中下标。

解题路线

1. 先考虑排序后的值 a1≤a2≤…≤an。最佳三数乘积只可能是最大三个 an·a(n−1)·a(n−2)，或最小两个 a1·a2 与最大 an 的乘积。两个大负数可相乘变成大正数，所以不能只取最大三个。
2. 一次扫描维护 high1/high2/high3 三个最大值与 low1/low2 两个最小值。每来一个数按次序更新两个极值链；这些值对应已扫描数组中的不同出现位置，即使数值相同也可作为不同位置。
3. 扫描完比较上述两个候选。若所有数为负，第一个候选可能仍是最大（最接近零）；公式不依赖正数存在。

手动走一遍

[-10,-10,1,2,3] 中最大三个给 1×2×3=6，两个最小值和最大值给 (-10)×(-10)×3=300，应返回 300。[-5,-4,-3,-2] 的候选分别为 -24 与 -40，最大是 -24。输入 [0,0,0] 返回 0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def max_three_product(nums: list[int]) -> int:
    """Maximum product of three distinct positions in one scan."""
    if len(nums) < 3:
        raise ValueError("at least three values are required")
    high1 = high2 = high3 = float("-inf")
    low1 = low2 = float("inf")
    for value in nums:
        if value >= high1:
            high1, high2, high3 = value, high1, high2
        elif value >= high2:
            high2, high3 = value, high2
        elif value > high3:
            high3 = value
        if value <= low1:
            low1, low2 = value, low1
        elif value < low2:
            low2 = value
    return int(max(high1 * high2 * high3, high1 * low1 * low2))

复杂度

N 个元素只扫描一次，每项常数次比较，时间 O(N)、辅助空间 O(1)。排序法 O(N log N) 时间，虽也容易讲清候选，但不满足题目 O(N) 目标。

易错点与追问

容易失分的边界

• 只维护最大三个数，漏掉两个负数翻正的大乘积。
• 在更新 high1 后忘记依次下移旧 high1/high2，导致三个极值来自不正确的历史状态。
• 将重复数值误当成同一个元素而禁止使用不同位置的同值。
• 在固定宽度整数语言中先用窄类型相乘，溢出后再转宽类型已晚。

继续深挖

• 若要返回三个下标，极值状态须同时保存值和原索引，并确保三处索引互异。
• 若输入改成任意 k 个数最大乘积，负数奇偶与零会令状态设计更复杂，不能直接沿用五个极值。
• 若是浮点输入，NaN、无穷大与负零的排序/乘法语义要先约定。