数组中两元素的最大乘积 图解题解
这道题到底在问什么
- 输入
- nums=[3,4,5,2]
- 输出
- 12
- 输入
- nums=[1,5,4,5]
- 输出
- 16
- 输入
- nums=[3,7]
- 输出
- 12
最优解：一步一步想明白
- 3记牢一句:挑出最大的两个数 max1、max2,答案就是 (max1-1)*(max2-1)。扫一遍同时维护最大和次大两个擂主即可。下面每帧都在套这句。
- 4画面摆好了。上面这一排是数组 nums = [3,1,5,2,6,4],右边擂台状态栏记着两个擂主,最大 max1 和次大 max2,现在都还没定,答案候选也在等次大出现。我们要做的就是扫一遍数组,把全场最大的两个数擂出来。先把内部比较门槛设为 0,画面暂时仍显示未定,开始上人。
- 5先把两个擂主的内部比较门槛都设成 0,但擂台上还没有真正的擂主,状态栏显示未定。为什么门槛是 0?因为题目保证每个数至少是 1,拿 0 当门槛,第一个上场的数一定能顶上去坐实擂主,不会出错。接下来从左到右,每来一个数都让它去打擂。
- 6打擂的规则就两句话。来一个新数,先看它能不能比 max1 还大,能的话,旧的 max1 就降级去当 max2,新数自己坐上 max1,旧擂主没被淘汰,只是退了一位;如果顶不掉 max1,就退一步看它能不能比 max2 大,能就更新 max2。两个擂主始终是目前见过最大的两个。下面正式开扫。
- 7轮到第 0 个数 3 上场。先看擂台现状,最大 max1 还未定,次大 max2 还未定。拿它先去冲 max1,冲不动再退一步冲 max2。
- 83 一来就顶过了 0 这道门槛,把还空着的 max1 坐实,3 坐上 max1。次大 max2 的位置暂时还没人,状态栏仍显示未定。绿色标出的就是现在唯一的擂主。
- 9轮到第 1 个数 1 上场。先看擂台现状,最大 max1 是 3,次大 max2 还未定。拿它先去冲 max1,冲不动再退一步冲 max2。
- 101 顶不掉 max1 3,退一步看次大。次大的位置本来还空着,1 就坐上 max2。现在两个擂主到齐了。
- 11轮到第 2 个数 5 上场。先看擂台现状,最大 max1 是 3,次大 max2 是 1。拿它先去冲 max1,冲不动再退一步冲 max2。
- 125 比当前的 max1 也就是 3 还大,顶掉成功。旧的 max1 3 降级去当 max2,新数 5 坐上 max1。绿色标出的就是现在的两个擂主。
- 13轮到第 3 个数 2 上场。先看擂台现状,最大 max1 是 5,次大 max2 是 3。拿它先去冲 max1,冲不动再退一步冲 max2。
- 142 既顶不掉 max1 5,也顶不掉 max2 3,它太小,擂台不收。两个擂主原封不动,继续往后扫。
- 15轮到第 4 个数 6 上场。先看擂台现状,最大 max1 是 5,次大 max2 是 3。拿它先去冲 max1,冲不动再退一步冲 max2。
- 166 比当前的 max1 也就是 5 还大,顶掉成功。旧的 max1 5 降级去当 max2,新数 6 坐上 max1。绿色标出的就是现在的两个擂主。
- 17轮到第 5 个数 4 上场。先看擂台现状,最大 max1 是 6,次大 max2 是 5。拿它先去冲 max1,冲不动再退一步冲 max2。
- 184 既顶不掉 max1 6,也顶不掉 max2 5,它太小,擂台不收。两个擂主原封不动,整排数都扫完了,下一帧套公式算答案。
- 19整排都扫完了,两个擂主稳稳定下来:最大 max1 是 6,在下标 4;次大 max2 是 5,在下标 2。绿色标出的就是全场最大的这两个数。剩下的就是套公式算答案了。
- 20套公式 (max1-1)*(max2-1)。先看最大的那个数 6,题目要求每个数先减一,所以 6 减 1 等于 5。这就是乘式的第一个因子。
- 21再看次大的那个数 5,同样先减一,5 减 1 等于 4。这是乘式的第二个因子。两个数都得各自减一,这一步最容易漏。
- 22两个因子相乘,5 乘以 4 等于 20。这就是最大乘积,跟开头说的答案一字不差。
- 23为什么一定取最大的两个?试着把次大 5 换成第三大的 4 算算看,(6减1) 乘以 (4减1) 等于 15,比 20 还小。因为两个因子都非负,任何一个换成更小的数,乘积只会变小。所以挑最大的两个数,答案才最大。
- 24回看整道题:扫一遍数组,一路维护最大 max1 和次大 max2 两个擂主,扫完拿到全场最大的两个数 6 和 5,各自减一再相乘,(6减1) 乘 (5减1) 得 20。一遍扫描就搞定,这就是这道题的全部。
⚠️ 容易写错的地方
✗ 错：直接拿最大两数相乘,忘了各自减一
✓ 对：答案是 (max1-1)*(max2-1),每个数都先减一再乘
题目定义的式子就是 (nums[i]-1)*(nums[j]-1),两个被选的数都要减去 1。比如最大两数是 6 和 5,正确答案是 (6-1)*(5-1)=20,不是 6*5=30。最常见的错就是看到「最大乘积」就把两个数直接乘起来
✗ 错：重复的最大值只算一次,漏掉第二个
✓ 对：相等的最大值要能落进次大 max2
两个下标只要不同,值可以相等。像 [1,5,4,5],最大两数是两个 5,答案是 (5-1)*(5-1)=16。维护时 max1 那关用严格大于,遇到等于 max1 的数顶不掉 max1,就会退一步更新 max2,正好把第二个最大值接住,这样重复的最大值就不会漏
✗ 错：max1、max2 初值设成第一个元素或随意的数
✓ 对：初值设 0(因为 nums[i]≥1)或负无穷
题目保证每个数 ≥ 1,所以两个擂主从 0 起步,第一个数一定能顶上去,逻辑最干净。如果随手设成一个很大的数,真实数据可能永远顶不掉,擂主就更新不出来,答案就错了
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def maxProduct(self, nums: List[int]) -> int:
ans = 0
for i, a in enumerate(nums):
for b in nums[i + 1 :]:
ans = max(ans, (a - 1) * (b - 1))
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maxProduct(vector<int>& nums) {
int ans = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ans = max(ans, (nums[i] - 1) * (nums[j] - 1));
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxProduct(int[] nums) {
int ans = 0;
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ans = Math.max(ans, (nums[i] - 1) * (nums[j] - 1));
}
}
return ans;
}
}复杂度
时间
O(n)
n 是数组长度。动画演示的优解只扫一遍,每个数做常数次比较来维护 max1、max2,所以是线性的 O(n)。参考代码区那版用两两枚举,是 O(n²),在 n ≤ 500 时也能轻松通过,但一遍扫描更快、更推荐
空间
O(1)
按峰值算。一遍扫描只用了 max1、max2 两个擂主变量,加上循环变量,都是常数空间,所以是 O(1)。枚举那版同样只用一个 ans 变量,也是 O(1)。两种写法都不需要额外的数组或排序结构
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组中两元素的最大乘积 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么答案是 (max1-1)*(max2-1),挑最大的两个数就对?+
因为每个数都 ≥ 1,减一之后是非负的,而且原数越大、减一后也越大,这个变换是单调的。两个非负数相乘,各自越大乘积越大。所以要让乘积最大,就该让两个因子各自最大,也就是挑出原数组里最大的两个数 max1、max2,再各自减一相乘。别忘了减一是题目定义的一部分,不能直接拿两个最大数相乘。
能不能不排序、一遍扫完就找出最大的两个数?+
能,这正是优解。扫一遍数组,维护两个擂主,max1 记当前最大、max2 记当前第二大。每来一个新数,先看它能不能比 max1 大,能就把旧 max1 降级当 max2、自己上位;否则再看能不能比 max2 大,能就更新 max2。一遍扫完,两个擂主就是全场最大的两个数,时间 O(n),比先排序的 O(n log n) 更快。
如果数组里最大值出现了重复,会不会出错?+
不会,反而要利用它。两个下标只要不同,值可以相等。比如 [1,5,4,5],最大的两个数就是两个 5,答案是 (5-1)*(5-1)=16。维护时让 max1 那一关用严格大于,等于 max1 的数顶不掉它,就会退一步去更新 max2,正好把第二个最大值接住,所以重复的最大值能被正确地算上两次。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组中两元素的最大乘积 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。