Every-Sublist-Min-Sum.md

题目地址（Every Sublist Min Sum）

https://binarysearch.com/problems/Every-Sublist-Min-Sum

题目描述

You are given a list of integers nums. Return the sum of min(x) for every sublist x in nums. Mod the result by 10 ** 9 + 7. Constraints n ≤ 100,000 where n is the length of nums Example 1 Input nums = [1, 2, 4, 3] Output 20 Explanation We have the following sublists and their mins: min([1]) = 1 min([1, 2]) = 1 min([1, 2, 4]) = 1 min([1, 2, 4, 3]) = 1 min([2]) = 2 min([2, 4]) = 2 min([2, 4, 3]) = 2 min([4]) = 4 min([4, 3]) = 3 min([3]) = 3 

前置知识

• 单调栈

公司

• 暂无

单调栈

思路

我们可以枚举得到答案。具体的枚举策略为：

• 假设以索引 0 的值为最小值且包含索引 0 的子数组个数 c0。 其对答案的贡献为 c0 * nums[0]
• 假设以索引 1 的值为最小值且包含索引 1 的子数组个数 c1。 其对答案的贡献为 c1 * nums[1]
• 。。。
• 假设以索引 n-1 的值为最小值且包含索引 n-1 的子数组个数 cn。其对答案的贡献为 cn * nums[n-1]

上述答案贡献之和即为最终答案。

接下来我们考虑分别如何计算上面的子贡献。

使用单调栈可以很容易地做到这一点，因为单调栈可以回答下一个（上一个）更小（大）的元素的位置这个问题。

对于 i 来说，我们想知道下一个更小的位置 r ，以及上一个更小的位置 l。 这样 i 对答案的贡献就是 (r-i)*(i-l)*nums[i]

代码上，我们处理到 i 的时候，不是计算 i 对答案的贡献，而是计算出从栈中弹出来的索引 last 对答案的贡献。这可以极大的简化代码。具体见下方代码区。

为了简化逻辑判断，我们可以使用单调栈常用的一个技巧：虚拟元素。这里我们可以往 nums 后面推入一个比所有 nums 的值都小的数即可。

关键点

• 分别计算以每一个被 pop 出来的为最小数的贡献

代码

代码支持：Python

Python3 Code:

classSolution: defsolve(self, nums): nums+= [float('-inf')] mod=10**9+7stack= [] ans=0fori, numinenumerate(nums): whilestackandnums[stack[-1]] >num: last=stack.pop() left=stack[-1] ifstackelse-1ans+= (i-last) * (last-left) *nums[last] stack.append(i) returnans%mod

复杂度分析

令 n 为 nums 长度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 46K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。