LeetCode 1464. 数组中两元素的最大乘积

2024-03-06 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1464. 数组中两元素的最大乘积

题意分析

给定一个整数数组 nums，要从中选出两个不同下标 $i \ne j$，最大化 $(nums[i] - 1) \times (nums[j] - 1)$，返回这个最大值。

目标式的形状值得先拆一拆：两个因子各自减 $1$，而减法是保序的单调变换——$a > b$ 必有 $a - 1 > b - 1$。所以「选哪两个数」这件事与减不减 $1$ 无关，减 $1$ 只影响最终乘出来的数值，不影响选择策略。

约束里写明 $1 \le nums[i] \le 10^3$，全是正数。这一条极其重要：它排除了「两个绝对值很大的负数相乘反而更大」这个常见陷阱，使得答案必定落在最大的两个元素身上。另一条是 $2 \le n \le 500$，数组至少有两个元素，所以不存在无解情形；$n$ 很小意味着排序也能过，但线性扫描显然更配得上这道题。

边界要注意两处：数组恰好只有两个元素时，答案就是这两个数各减一后的乘积，没有选择余地；元素允许重复，nums = [3, 3] 时两个 $3$ 分处不同下标，是合法的一对，答案是 $4$——不能因为值相同就把其中一个排除掉。

解法：一次扫描维护最大两值

核心思路

暴力做法是双层循环枚举所有 $i < j$ 的组合，逐对计算 $(nums[i]-1)(nums[j]-1)$ 取最大，代价 $O(n^2)$。$n = 500$ 时不过 $12$ 万次，其实能过——但瓶颈在于它没有利用题目的结构，一旦 $n$ 提到 $10^5$ 就崩。

关键观察分两步。第一步，由于所有元素 $\ge 1$，减 $1$ 后所有因子 $\ge 0$，两个非负数的乘积随任一因子增大而不减，所以要让乘积最大就要让两个因子都尽可能大。第二步，减 $1$ 是保序的，因子最大等价于原值最大。两步合起来得到：答案必然取自数组中最大的两个元素（按下标计重，即最大值和次大值）。

有了这个结论，问题从「枚举 $O(n^2)$ 对」降级为「求 Top-2」。排序后取末两位是 $O(n \log n)$，但求 Top-2 根本不需要全序信息，一趟扫描就够。

于是本解法维护两个变量，其含义就是全程的不变量：扫描到下标 $i$ 时，first 是 nums[0..i] 中的最大值，second 是其中的次大值（允许与 first 数值相等，但来自不同下标）。「允许相等」这句必须写死在定义里——nums = [3, 3] 时 first = second = 3 才是正确状态。

维护这个不变量的分支只有两种情况：新元素比 first 还大，则原来的 first 顺位降为 second，新元素登顶；新元素夹在 second 与 first 之间（含等于 first 的情形），则只刷新 second。两个分支必须用 else if 串起来，因为第一个分支已经把 second 更新过了，再落进第二个分支会把 second 覆盖成新元素本身，等于同一个下标被用了两次。

解题步骤

用前两个元素初始化：first = max(nums[0], nums[1])、second = min(nums[0], nums[1])。为什么不能像求最大值那样初始化成 $0$ 或极小值？因为 second 的语义是「第二大」，必须由两个真实存在的下标垫底；用哨兵初始化在 $n = 2$ 时会得到错误的配对。题目保证 $n \ge 2$，所以这样取初值总是安全的。

循环从 $i = 2$ 起遍历剩余元素，因为前两个已经被初值消化掉了，从 $0$ 开始会让 nums[0] 与 nums[1] 被重复计入。

若 num > first，先执行 second = first 再执行 first = num。顺序不能反：先改 first 会让 second 拿到新元素自己，退化成同一个数配对。这一步的语义是「冠军被顶下来变成亚军」，被顶下的旧冠军仍然是一个合法的、不同下标的元素。

否则若 num > second，执行 second = num。用 else if 而不是两个独立 if，理由如上一条所述。这里的比较用 > 而非 >= 不影响正确性——相等时不更新，second 保留的是同样大小的另一个元素，结果一致。

返回 (first - 1) * (second - 1)。乘积最大约为 $999 \times 999 = 998001$，远在 int 范围内，不需要 long。

以 nums = [3, 4, 5, 2] 走一遍：

初始化：比较 nums[0] = 3 与 nums[1] = 4，得 first = 4、second = 3。此时不变量对 [3, 4] 成立。
$i = 2$：num = 5，$5 > 4$ 命中第一个分支，先 second = first = 4，再 first = 5。状态 first = 5, second = 4，正是 [3, 4, 5] 的最大两值。
$i = 3$：num = 2，$2 > 5$ 不成立，$2 > 4$ 也不成立，两个分支都不进，状态不变。
返回 $(5 - 1) \times (4 - 1) = 4 \times 3 = 12$。

再看一个重复值的用例 nums = [3, 7, 3, 7]：初值 first = 7, second = 3；$i = 2$ 时 num = 3，$3 > 7$ 否，$3 > 3$ 否，不动；$i = 3$ 时 num = 7，$7 > 7$ 否，但 $7 > 3$ 成立，second = 7。返回 $6 \times 6 = 36$。这里 second 被更新成与 first 相等的值，正是「不同下标可以取相同数值」的体现——若第二个分支写成 num > second && num < first，second 会停在 $3$，错答成 $12$。

代码实现

class Solution {
    public int maxProduct(int[] nums) {
        // second 语义是「次大值」，必须由两个真实下标垫底，故用前两个元素初始化。
        int first = Math.max(nums[0], nums[1]);
        int second = Math.min(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int num = nums[i];
            if (num > first) {
                // 旧冠军降为亚军，它仍是一个合法的不同下标元素。
                second = first;
                first = num;
            } else if (num > second) {
                // 必须是 else if，否则上一分支刚更新的 second 会被覆盖成 num 自己。
                second = num;
            }
        }

        return (first - 1) * (second - 1);
    }
}

func maxProduct(nums []int) int {
    // second 语义是「次大值」，必须由两个真实下标垫底，故用前两个元素初始化。
    first, second := nums[0], nums[1]
    if first < second {
        first, second = second, first
    }

    for i := 2; i < len(nums); i++ {
        num := nums[i]
        if num > first {
            // 旧冠军降为亚军，它仍是一个合法的不同下标元素。
            second = first
            first = num
        } else if num > second {
            // 必须是 else if，否则上一分支刚更新的 second 会被覆盖成 num 自己。
            second = num
        }
    }

    return (first - 1) * (second - 1)
}

复杂度分析

时间复杂度：$O(n)$。每个元素只被访问一次，循环体内最多两次比较和两次赋值，全是常数操作；相比排序法省下了 $\log n$ 因子，相比暴力枚举省下了一整个数量级。

空间复杂度：$O(1)$。只用了 first、second、num 三个整型变量，不复制数组也不排序（排序法若不允许原地修改输入还要额外 $O(n)$ 拷贝）。

关键点总结

目标函数带单调变换时先把变换剥掉。$x \mapsto x - 1$ 保序，所以「最大化 $(a-1)(b-1)$」与「选最大的两个数」等价；能识别这一步，问题就从枚举降级为选取。

判断能否贪心取极值，先确认符号范围。本题全正才使得 Top-2 一定最优；若允许负数，还要同时考虑最小的两个数（两负相乘为正），这正是「三个数的最大乘积」的核心分歧点。

求 Top-K 不需要全序。$K$ 很小时用 $K$ 个滚动变量一趟扫描即可，$O(n)$ 优于排序的 $O(n\log n)$，也优于堆的 $O(n \log K)$ 常数。

次大值的初始化必须由真实元素承担，不能用哨兵。凡是「第二/第三大」这类状态，初值都得从前 $K$ 个元素直接构造，否则元素数恰为 $K$ 时会配出不存在的下标。

面试视角：这题真正的考点是两个追问。一是「如果数组含负数怎么办」，要答出需同时跟踪最小两值并比较两种乘积；二是「如果要求第 $k$ 大的两个数或 Top-K」，要答出 $K$ 小用变量、$K$ 大用小顶堆或快速选择。能主动指出「减 1 是保序变换所以不影响选择」，会显得基本功扎实。

易错点总结

两个更新分支写成两个独立 if：nums = [1, 2, 3] 时 $i = 2$ 处 num = 3，第一个 if 把 second 置为 $2$、first 置为 $3$，紧接着第二个 if 判 $3 > 2$ 成立又把 second 改成 $3$，返回 $2 \times 2 = 4$，正确答案是 $2 \times 1 = 2$。

登顶时先改 first 再改 second：nums = [1, 2, 3] 中 first = 3 后 second = first = 3，返回 $4$ 而非 $2$，同一个元素被用了两次。

second 初始化为 0 或 Integer.MIN_VALUE 且循环从 $i = 0$ 起：nums = [5, 5] 时若逻辑写成只在 num > first 时下沉，第二个 $5$ 不大于 first，second 停在初值 $0$，返回 $4 \times (-1) = -4$，正确答案是 $16$。

第二个分支加上 num < first 的额外条件：nums = [3, 7, 3, 7] 时第二个 $7$ 被拒，second 停在 $3$，返回 $12$，正确答案是 $36$。

返回时只给一个因子减 1：写成 (first - 1) * second，nums = [3, 4, 5, 2] 会返回 $4 \times 4 = 16$，正确答案是 $12$。

循环从 $i = 0$ 开始而初值已吃掉前两个元素：nums = [2, 3] 时 first = 3, second = 2，$i = 0$ 处 num = 2 不动，$i = 1$ 处 num = 3，$3 > 3$ 否但 $3 > 2$ 成立，second = 3，返回 $4$，正确答案是 $2$。

排序后取 nums[n-1] 与 nums[n-2] 却写成 nums[0] 与 nums[1]：nums = [1, 5, 4, 5] 升序后取头两个得 $(1-1)(4-1) = 0$，正确答案是 $16$。

误以为可以取同一个下标两次：nums = [2, 4] 若允许 first 自乘会返回 $9$，题目要求 $i \ne j$，正确答案是 $3$。

对含负数的输入照搬本解法：虽然本题保证正数，但把这段代码复用到允许负数的场景时，nums = [-10, -9, 1, 2] 会返回 $(2-1)(1-1) = 0$，而 $(-10-1)(-9-1) = 110$ 更大。

相似题目

题目	难度	考察点
628. 三个数的最大乘积	简单	允许负数，须同时跟踪最大三值与最小两值，比较两种组合
414. 第三大的数	简单	Top-3 且要求严格去重，相等值不能占两个名次，边界判定更细
215. 数组中的第K个最大元素	中等	$K$ 任意大，滚动变量失效，需快速选择或小顶堆
152. 乘积最大子数组	中等	求的是连续子数组乘积，负号翻转需同时维护最大与最小乘积做 DP
1679. K 和数对的最大数目	中等	同为从数组中挑配对，但要挑最多对且和固定，需哈希计数或双指针
164. 最大间距	中等	求排序后相邻最大差，无法靠常数个滚动变量，需桶排序达到线性
347. 前 K 个高频元素	中等	Top-K 的对象是频次而非原值，需先计数再桶排或堆选
面试题 16.07. 最大数值	简单	同为取两数最大，但禁用比较运算符，考位运算与符号提取