笔试真题复盘：无序数组里找三个数，乘积最大，要求 O(n)

图 1：本文封面，三个正数与两负一正两条路线谁大听谁的。

先说明属性：这是一篇历史笔试题复盘，题目出自本地历史笔试资料，与任何公司的当前招聘无关。题面很短：给定一个无序数组，里面混着正数、负数和零，找出三个数使乘积最大，要求时间复杂度 O(n)、空间复杂度 O(1)。考点不在「找三个大数」，而在那个容易被忽略的负数。

第一步，先把答案的形态数清楚。

如果数组全是正数，答案显然是最大的三个数相乘。但一旦有负数，局面就变了：两个负数相乘得正，而且绝对值越大的负数乘出来的正数越大。所以「最小的两个负数」乘上「最大的那个正数」，完全可能超过「三个最大数」的乘积。

推演一下就会发现，无论数组里正负零怎么混，最优解只可能落在两种形态上：

• 形态一：最大的三个数相乘（m1 × m2 × m3）。
• 形态二：最小的两个数乘最大的一个数（s1 × s2 × m1），通常对应两个大负数配一个大正数。

为什么不存在第三种形态？三个数里若只含一个负数，乘积为负，不可能赢过任何非负候选；若含两个负数，第三个必须取尽可能大的正数，即 m1；若含零个或三个负数，归入形态一讨论。两种形态取较大者，就是答案。

第二步，用五个变量一趟扫出来。

排序也能解：排完取首尾组合，但那是 O(n log n)，不满足题面要求。O(n) 的做法是一趟扫描，滚动维护五个极值：最大、次大、第三大（m1、m2、m3）和最小、次小（s1、s2）。每个元素最多参与五次比较，全程常量空间。这也是在线流式场景的唯一出路——数据只来一遍，没机会回头排序。

下面这份实现内置题面用例、含负数用例和 2000 组随机数组对拍，用 Node.js 22.15.0 直接运行（node maxproduct.js）：

'use strict';

// 一趟扫描维护五个极值：最大三个 + 最小两个
function maxProductOfThree(a) {
  if (a.length < 3) throw new RangeError('数组至少需要 3 个元素');
  let m1 = -Infinity, m2 = -Infinity, m3 = -Infinity; // 最大、次大、第三大
  let s1 = Infinity, s2 = Infinity; // 最小、次小
  for (const x of a) {
    if (x > m1) { m3 = m2; m2 = m1; m1 = x; }
    else if (x > m2) { m3 = m2; m2 = x; }
    else if (x > m3) { m3 = x; }
    if (x < s1) { s2 = s1; s1 = x; }
    else if (x < s2) { s2 = x; }
  }
  return Math.max(m1 * m2 * m3, s1 * s2 * m1);
}

// 暴力枚举作对照
function brute(a) {
  let best = -Infinity;
  for (let i = 0; i < a.length; i++)
    for (let j = i + 1; j < a.length; j++)
      for (let k = j + 1; k < a.length; k++)
        best = Math.max(best, a[i] * a[j] * a[k]);
  return best;
}

console.log(`题面用例 [3,4,1,2] -> ${maxProductOfThree([3, 4, 1, 2])}`);
console.log(`含负数 [-8,-6,1,3,9] -> ${maxProductOfThree([-8, -6, 1, 3, 9])}（两负一正路线胜出）`);
console.log(`含零 [0,-1,-2,-3] -> ${maxProductOfThree([0, -1, -2, -3])}`);
console.log(`全负 [-5,-4,-3,-2] -> ${maxProductOfThree([-5, -4, -3, -2])}`);

// 随机对拍：与暴力枚举逐个比对
let ok = true;
for (let t = 0; t < 2000; t++) {
  const n = 3 + Math.floor(Math.random() * 12);
  const arr = Array.from({ length: n }, () => Math.floor(Math.random() * 21) - 10);
  if (maxProductOfThree(arr) !== brute(arr)) { ok = false; console.log('不一致:', arr); break; }
}
console.log(`2000 组随机数组对拍：${ok ? '全部一致' : '发现不一致'}`);
try { maxProductOfThree([1, 2]); } catch (e) { console.log(`边界拦截：${e.message}`); }

实测输出：

题面用例 [3,4,1,2] -> 24
含负数 [-8,-6,1,3,9] -> 432（两负一正路线胜出）
含零 [0,-1,-2,-3] -> 0
全负 [-5,-4,-3,-2] -> -24
2000 组随机数组对拍：全部一致
边界拦截：数组至少需要 3 个元素

注意含负数那组：三个最大数 1、3、9 乘起来只有 27，而 −8 × −6 × 9 = 432，差了 16 倍——这就是不维护「最小两个」会踩的坑。2000 组随机数组与暴力枚举逐一对拍全部一致，比口头论证更有说服力。

图 2：一趟扫描维护五个极值，两种候选取大。

可能的追问。

「为什么两种形态里都出现 m1？」形态二里两个负数定下来之后，第三个数要最大化乘积就必须取全数组最大值，所以 m1 是公共项。「零会捣乱吗？」不会，零只是让乘积变零，五种极值的滚动更新逻辑天然兼容。「如果要求的是和最大而不是积最大呢？」那就只需要最大三个数，负数的对称性消失了——乘积题的全部难点就在符号的对称性上。「空间真的是 O(1) 吗？」是，无论数组多长，手里始终只有五个变量。

这套「只扫一遍、只维护几个极值」的思路，在工程里对应的是在线统计：流式计算里的在线最大最小值、分位数骨架、蓄水池采样，都是同一个范式——数据只来一次，状态必须压到常量级。回到笔试现场，建议的答题节奏：先讲「负数两两得正」推出的两种候选形态，再给出五变量一趟扫的实现，最后主动补对拍验证与边界处理。你写极值滚动这类代码时翻过车吗？最常见的坑是不是忘了初始值的正负无穷？欢迎聊聊。