题目描述
思路解析动画文字版
记牢一句:挑出最大的两个数 max1、max2,答案就是 (max1-1)*(max2-1)。扫一遍同时维护最大和次大两个擂主即可。下面每帧都在套这句。
总览 · 数组 + 擂台状态栏：画面摆好了。上面这一排是数组 nums = [3,1,5,2,6,4],右边擂台状态栏记着两个擂主,最大 max1 和次大 max2,现在都还没定,答案候选也在等次大出现。我们要做的就是扫一遍数组,把全场最大的两个数擂出来。先把内部比较门槛设为 0,画面暂时仍显示未定,开始上人。
初始化 · 擂主未定,比较门槛设 0：先把两个擂主的内部比较门槛都设成 0,但擂台上还没有真正的擂主,状态栏显示未定。为什么门槛是 0?因为题目保证每个数至少是 1,拿 0 当门槛,第一个上场的数一定能顶上去坐实擂主,不会出错。接下来从左到右,每来一个数都让它去打擂。
打擂规则 · 先冲 max1,冲不动再冲 max2：打擂的规则就两句话。来一个新数,先看它能不能比 max1 还大,能的话,旧的 max1 就降级去当 max2,新数自己坐上 max1,旧擂主没被淘汰,只是退了一位;如果顶不掉 max1,就退一步看它能不能比 max2 大,能就更新 max2。两个擂主始终是目前见过最大的两个。下面正式开扫。
看 nums[0] = 3：轮到第 0 个数 3 上场。先看擂台现状,最大 max1 还未定,次大 max2 还未定。拿它先去冲 max1,冲不动再退一步冲 max2。
第 0 个数 · 更新擂主：3 一来就顶过了 0 这道门槛,把还空着的 max1 坐实,3 坐上 max1。次大 max2 的位置暂时还没人,状态栏仍显示未定。绿色标出的就是现在唯一的擂主。
看 nums[1] = 1：轮到第 1 个数 1 上场。先看擂台现状,最大 max1 是 3,次大 max2 还未定。拿它先去冲 max1,冲不动再退一步冲 max2。
第 1 个数 · 更新擂主：1 顶不掉 max1 3,退一步看次大。次大的位置本来还空着,1 就坐上 max2。现在两个擂主到齐了。
看 nums[2] = 5：轮到第 2 个数 5 上场。先看擂台现状,最大 max1 是 3,次大 max2 是 1。拿它先去冲 max1,冲不动再退一步冲 max2。
第 2 个数 · 更新擂主：5 比当前的 max1 也就是 3 还大,顶掉成功。旧的 max1 3 降级去当 max2,新数 5 坐上 max1。绿色标出的就是现在的两个擂主。
看 nums[3] = 2：轮到第 3 个数 2 上场。先看擂台现状,最大 max1 是 5,次大 max2 是 3。拿它先去冲 max1,冲不动再退一步冲 max2。
第 3 个数 · 擂主不变：2 既顶不掉 max1 5,也顶不掉 max2 3,它太小,擂台不收。两个擂主原封不动,继续往后扫。
看 nums[4] = 6：轮到第 4 个数 6 上场。先看擂台现状,最大 max1 是 5,次大 max2 是 3。拿它先去冲 max1,冲不动再退一步冲 max2。
第 4 个数 · 更新擂主：6 比当前的 max1 也就是 5 还大,顶掉成功。旧的 max1 5 降级去当 max2,新数 6 坐上 max1。绿色标出的就是现在的两个擂主。
看 nums[5] = 4：轮到第 5 个数 4 上场。先看擂台现状,最大 max1 是 6,次大 max2 是 5。拿它先去冲 max1,冲不动再退一步冲 max2。
第 5 个数 · 擂主不变：4 既顶不掉 max1 6,也顶不掉 max2 5,它太小,擂台不收。两个擂主原封不动,整排数都扫完了,下一帧套公式算答案。
扫描完成 · 最大两数 = 6 和 5：整排都扫完了,两个擂主稳稳定下来:最大 max1 是 6,在下标 4;次大 max2 是 5,在下标 2。绿色标出的就是全场最大的这两个数。剩下的就是套公式算答案了。
套公式 · 先算 max1 减一：套公式 (max1-1)*(max2-1)。先看最大的那个数 6,题目要求每个数先减一,所以 6 减 1 等于 5。这就是乘式的第一个因子。
套公式 · 再算 max2 减一：再看次大的那个数 5,同样先减一,5 减 1 等于 4。这是乘式的第二个因子。两个数都得各自减一,这一步最容易漏。
相乘 · 答案 = 20：两个因子相乘,5 乘以 4 等于 20。这就是最大乘积,跟开头说的答案一字不差。
反证 · 换掉次大反而更小：为什么一定取最大的两个?试着把次大 5 换成第三大的 4 算算看,(6减1) 乘以 (4减1) 等于 15,比 20 还小。因为两个因子都非负,任何一个换成更小的数,乘积只会变小。所以挑最大的两个数,答案才最大。
完成 · 最大乘积 = 20：回看整道题:扫一遍数组,一路维护最大 max1 和次大 max2 两个擂主,扫完拿到全场最大的两个数 6 和 5,各自减一再相乘,(6减1) 乘 (5减1) 得 20。一遍扫描就搞定,这就是这道题的全部。
边界:长度为 2 时两数全选;重复最大值都要用上(靠次大能接相等值);含 1 时若有更大的数会被挤掉(长度为 2 或全是 1 时仍要选上)。
面试重点:减一单调故挑最大两数;一遍扫描维护 max1、max2 即 O(n);重复最大值靠 max1 用严格大于能落进次大,正确算两次。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(n)，n 是数组长度。动画演示的优解只扫一遍,每个数做常数次比较来维护 max1、max2,所以是线性的 O(n)。参考代码区那版用两两枚举,是 O(n²),在 n ≤ 500 时也能轻松通过,但一遍扫描更快、更推荐
- 空间：O(1)，按峰值算。一遍扫描只用了 max1、max2 两个擂主变量,加上循环变量,都是常数空间,所以是 O(1)。枚举那版同样只用一个 ans 变量,也是 O(1)。两种写法都不需要额外的数组或排序结构
易错点
面试追问把动画讲成自己的话
追问为什么答案是 (max1-1)*(max2-1),挑最大的两个数就对?
追问能不能不排序、一遍扫完就找出最大的两个数?
追问如果数组里最大值出现了重复,会不会出错?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
会议室 II
LeetCode 253 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题