题目描述
思路解析动画文字版
记住这条主线:答案 = (当最大值的贡献和) 减 (当最小值的贡献和),每份都用单调栈一遍扫出来。下面先跑第一遍:当最大值。
第一遍:求每个元素当最大值的贡献。柱高 = 元素值,柱下数字 = 下标。维护一个单调栈:栈里下标对应的高度从栈底到栈顶递减。新来一个值,只要栈顶比它矮(严格小于),就说明栈顶元素当最大值的右边界到了,结算它的贡献并弹出。
轮到下标 0(高 3,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 0 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 0。
轮到下标 1(高 1,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 1 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 0。
轮到下标 2(高 2,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
栈顶下标 1(高 1,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=1,向右到第一个严格大于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 1×1=1 个,贡献 1×1×1=1。累加后最大值贡献和 = 1。弹出下标 1。
栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 2 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 1。
轮到下标 3(高 4,紫色)。先看栈顶:有没有比它矮、正等着「右边第一个更大值」的元素。
栈顶下标 2(高 2,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=2,向右到第一个严格大于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 2×1=2 个,贡献 2×2×1=4。累加后最大值贡献和 = 5。弹出下标 2。
栈顶下标 0(高 3,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=1,向右到第一个严格大于它的元素的距离 right=3(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 1×3=3 个,贡献 3×1×3=9。累加后最大值贡献和 = 14。弹出下标 0。
栈顶不再比当前值矮(或栈已空),停止弹栈。把下标 3 压栈,让它去等自己右边第一个更大的值。当前最大值贡献和 = 14。
数组扫完,补一个高度无穷大的虚拟哨兵收尾:它比栈里任何元素都大,逼着把栈里还没结算的元素全部弹出结算(它们的右边界就是数组末尾)。
栈顶下标 3(高 4,标红)被当前值压倒:它向左到第一个不小于它的元素的距离 left=4,向右到第一个严格大于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最大值的子数组有 4×1=4 个,贡献 4×4×1=16。累加后最大值贡献和 = 30。弹出下标 3。
哨兵把栈清空,第一遍结束:所有元素当最大值的贡献已全部累加,最大值贡献和 = 30。
第一遍得到最大值贡献和 = 30。第二遍把判断方向反过来:求每个元素当最小值的贡献。这次栈里高度从栈底到栈顶递增,新来一个值,只要栈顶比它高(严格大于)就结算并弹出。贡献公式同样是 nums[j]×left×right,只是归属方向反过来:left 是向左到第一个不大于它的元素的距离、right 是向右到第一个严格小于它的元素的距离(同样一侧含相等、一侧不含,保证相等值不重复算)。
轮到下标 0(高 3,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
栈顶不再比当前值高(或栈已空),停止弹栈,把下标 0 压栈。当前最小值贡献和 = 0。
轮到下标 1(高 1,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
栈顶下标 0(高 3,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=1、向右到第一个严格小于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 1×1=1 个,贡献 3×1×1=3。累加后最小值贡献和 = 3。弹出下标 0。
栈顶不再比当前值高(或栈已空),停止弹栈,把下标 1 压栈。当前最小值贡献和 = 3。
轮到下标 2(高 2,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
栈顶不再比当前值高(或栈已空),停止弹栈,把下标 2 压栈。当前最小值贡献和 = 3。
轮到下标 3(高 4,紫色)。看栈顶:有没有比它高、正等着「右边第一个更小值」的元素。
栈顶不再比当前值高(或栈已空),停止弹栈,把下标 3 压栈。当前最小值贡献和 = 3。
再补一个高度负无穷的虚拟哨兵收尾:它比栈里任何元素都小,逼着把栈里还没结算的元素全部弹出结算。
栈顶下标 3(高 4,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=1、向右到第一个严格小于它的元素的距离 right=1(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 1×1=1 个,贡献 4×1×1=4。累加后最小值贡献和 = 7。弹出下标 3。
栈顶下标 2(高 2,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=1、向右到第一个严格小于它的元素的距离 right=2(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 1×2=2 个,贡献 2×1×2=4。累加后最小值贡献和 = 11。弹出下标 2。
栈顶下标 1(高 1,标红)被当前值压低:它向左到第一个不大于它的元素的距离 left=2、向右到第一个严格小于它的元素的距离 right=3(一侧含相等、一侧不含,保证相等值不重复算)。它当最小值的子数组有 2×3=6 个,贡献 1×2×3=6。累加后最小值贡献和 = 17。弹出下标 1。
第二遍结束:所有元素当最小值的贡献已累加,最小值贡献和 = 17。
两遍都跑完:最大值贡献和 = 30,最小值贡献和 = 17。答案 = 30 减 17 = 13,与开头给的 13 一致。整个过程只扫了两遍数组,每个下标进出栈各两次,所以是 O(n)。
边界:单元素与全相等都为 0;含负数照样正确,栈按原值比较。
面试常考:严格不等保证不重不漏;它是 lc907 的「最大 + 最小」双份版。
参考代码
from typing import Listclass Solution: def subArrayRanges(self, nums: List[int]) -> int: n = len(nums) def sum_max() -> int: st = [] total = 0 for i in range(n + 1): cur = float('inf') if i == n else nums[i] while st and nums[st[-1]] < cur: j = st.pop() total += nums[j] * (j - (st[-1] if st else -1)) * (i - j) st.append(i) return total def sum_min() -> int: st = [] total = 0 for i in range(n + 1): cur = float('-inf') if i == n else nums[i] while st and nums[st[-1]] > cur: j = st.pop() total += nums[j] * (j - (st[-1] if st else -1)) * (i - j) st.append(i) return total return sum_max() - sum_min()复杂度
- 时间：O(n)，两遍扫描,每遍里每个下标最多进栈一次、出栈一次,均摊 O(n);两遍合计仍是 O(n)
- 空间：O(n)，单调栈最坏(严格单调时)装下全部 n 个下标
易错点
面试追问把动画讲成自己的话
追问怎么避免相等元素被重复或漏算?
追问这题和「子数组最小值之和 lc907」是什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从字符串中移除星号
LeetCode 2390 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题