# 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:

```py

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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/pjrcm6.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/every-sublist-min-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.