给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。
示例：
输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
提示：
1 <= A <= 30000
1 <= A[i] <= 30000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-subarray-minimums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：# 单调栈，三次遍历(Python)
双层暴力求解所有的子数组，然后每个子数组再一层遍历找出最小肯定会超时的。我们考虑优化，我们有必要求出所有的子数组才能够求解么？应该是不需要的。
我们的想法是维护两个数组left和right
- left[i] 表示从左往右 第一个A[i] 小的元素的下标
- right[i] 表示从右往左 第一个不比A[i] 大的元素的下标
- 最终我们只需要计算 A[i] * (i - left[i]) * (right[i] - i) 的和即可（笛卡尔集）
对于left和right我们可以用单调栈生成
> 有多个题目都有类似的逻辑。
# Code
```python
#
# @lc app=leetcode.cn id=907 lang=python3
#
# [907] 子数组的最小值之和
#
# @lc code=start
class Solution:
def sumSubarrayMins(self, A: List[int]) -> int:
n = len(A)
minStack = []
left = [0] * n
right = [0] * n
res = 0
# [71,55,82,55]
for i, a in enumerate(A):
while minStack and a <= A[minStack[-1]]:
minStack.pop()
# edge case
if not minStack:
left[i] = -1
else:
left[i] = minStack[-1]
minStack.append(i)
minStack = []
for i, a in reversed(list(enumerate(A))):
while minStack and a < A[minStack[-1]]:
minStack.pop()
# edge case
if not minStack:
right[i] = n
else:
right[i] = minStack[-1]
minStack.append(i)
for i, a in enumerate(A):
res += a * (i - left[i]) * (right[i] - i)
print(left, right)
return res % 1000000007
# @lc code=end
```
LeetCode题解计算机为什么是基于二进制的？可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈
LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924
LeetCode题解微信红包微信红包 如何分配 让每个人在数学期望上是一样的？在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。 它反映随机变量平均取值的大小。 需要注意的是，期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。 期望值是该变量输出值的平均数。