算法题：Every Sublist Min Sum

Question

题目描述

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

题目地址

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

前置知识

• 单调栈

公司

• 暂无

单调栈

思路

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

• 假设以索引 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)$