题目描述
思路解析动画文字版
记住「每个元素当最小值,向两边扩到比它小为止,算 值×区间和」,下面每帧都在套它。
轮到 nums[0] = 3 当最小值。从它出发向左、向右扩展,只要邻居 ≥ 3 就纳入区间(区间里它最小)。
3 的最大区间是 [0, 0](绿色),和 3,最小乘积 3×3 = 9。比之前大,刷新最大为 9。
轮到 nums[1] = 1 当最小值。从它出发向左、向右扩展,只要邻居 ≥ 1 就纳入区间(区间里它最小)。
向左看 nums[0] = 3,不小于 1,纳入区间,左界扩到 0。
向右看 nums[2] = 5,不小于 1,纳入区间,右界扩到 2。
向右看 nums[3] = 6,不小于 1,纳入区间,右界扩到 3。
向右看 nums[4] = 4,不小于 1,纳入区间,右界扩到 4。
向右看 nums[5] = 2,不小于 1,纳入区间,右界扩到 5。
1 的最大区间是 [0, 5](绿色),和 21,最小乘积 1×21 = 21。比之前大,刷新最大为 21。
轮到 nums[2] = 5 当最小值。从它出发向左、向右扩展,只要邻居 ≥ 5 就纳入区间(区间里它最小)。
向右看 nums[3] = 6,不小于 5,纳入区间,右界扩到 3。
5 的最大区间是 [2, 3](绿色),和 11,最小乘积 5×11 = 55。比之前大,刷新最大为 55。
轮到 nums[3] = 6 当最小值。从它出发向左、向右扩展,只要邻居 ≥ 6 就纳入区间(区间里它最小)。
6 的最大区间是 [3, 3](绿色),和 6,最小乘积 6×6 = 36。没超过当前最大 55,保持。
轮到 nums[4] = 4 当最小值。从它出发向左、向右扩展,只要邻居 ≥ 4 就纳入区间(区间里它最小)。
向左看 nums[3] = 6,不小于 4,纳入区间,左界扩到 3。
向左看 nums[2] = 5,不小于 4,纳入区间,左界扩到 2。
4 的最大区间是 [2, 4](绿色),和 15,最小乘积 4×15 = 60。比之前大,刷新最大为 60。
轮到 nums[5] = 2 当最小值。从它出发向左、向右扩展,只要邻居 ≥ 2 就纳入区间(区间里它最小)。
向左看 nums[4] = 4,不小于 2,纳入区间,左界扩到 4。
向左看 nums[3] = 6,不小于 2,纳入区间,左界扩到 3。
向左看 nums[2] = 5,不小于 2,纳入区间,左界扩到 2。
2 的最大区间是 [2, 5](绿色),和 17,最小乘积 2×17 = 34。没超过当前最大 60,保持。
扫完每个元素当最小值的情形,最大的一个是 nums[4]=4 管区间 [2, 4](5、6、4),4×15 = 60。答案 60(最终再对 1e9+7 取模)。
边界先想清:单元素、全相等、被中间小值隔开。
面试重点:讲清单调栈如何一次定边界 + 前缀和的作用。
参考代码
from typing import Listclass Solution: def maxSumMinProduct(self, nums: List[int]) -> int: MOD = 10**9 + 7 prefix = [0] for x in nums: prefix.append(prefix[-1] + x) stack = [] best = 0 for i in range(len(nums) + 1): cur = nums[i] if i < len(nums) else 0 while stack and nums[stack[-1]] > cur: mid = stack.pop() left = stack[-1] + 1 if stack else 0 total = prefix[i] - prefix[left] best = max(best, total * nums[mid]) stack.append(i) return best % MOD复杂度
- 时间:O(n),单调栈每个元素进出各一次 + 前缀和
- 空间:O(n),前缀和数组 + 栈
易错点
面试追问把动画讲成自己的话
追问单调栈具体怎么一次求出每个元素的左右边界?
追问为什么要前缀和?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
子数组范围和
LeetCode 2104 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题