Links

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:
class Solution:
def solve(self, nums):
nums += [float('-inf')]
mod = 10 ** 9 + 7
stack = []
ans = 0
for i, num in enumerate(nums):
while stack and nums[stack[-1]] > num:
last = stack.pop()
left = stack[-1] if stack else -1
ans += (i - last) * (last - left) * nums[last]
stack.append(i)
return ans % mod
复杂度分析
令 n 为 nums 长度
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 46K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。