LiaoyiLeetCode 907. 子数组的最小值之和 中等
题目描述
给定一个整数数组 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
搬运 jack-108大佬的题解：
既然是求子数组中最小值的和，就是求 以 A[i] 作为最小数能构成的数组有多少个。
比如 [2,4,1,2] ,以1 为最小数。能构成的数组数为 (2+1)*(1+1) ，2 表示 1 左面有两个比它大的数，1 表示 1 右面有一个比它大的数。
用单调栈求出 A[i] 对应的左右最近比 A[i] 小的数，记索引为 prev,next，A[i] 为最小数能形成的数组为
(i - prev[i]) * (next[i] - i);
这里为什么没有加 1 了呢，因为 prev[i]已经是比 A[i] 小的数了，能和 A[i] 形成数组的都是比 A[i] 大的数。
我的解题方式：
注释已经足够详细，还是补充一下，我参考了大佬的解题代码，只不过我是直接求出来了以当前 A[i] 为最小值的子数组左右两边 大于或等于当前值的个数。这样后续求和直接相乘即可。（不过这里要强调一下，如果左边设置大于等于了，右边就只能是大于了，不然会重复计算相等的值）
开始有点看不懂大佬为啥左边初始化为 -1，右边初始化为 A.length 。假如我们遇到了这种情况，左边都比当前 A[i] 要大，那我们维护的单调递减栈就会不断出栈，不断出栈，直到栈为空为止，此时左边个数应该为 i+1（从 0 开始计数嘛），那么这部分大佬设为 -1 就很巧妙了，问题也就自然明白啦，个人感觉自己写的还是比较好理解一点，不然直接弄一个 -1 ，第一次用单调栈，还是不太熟...
那么对于右边初始化为 A.length ，也是同理啦，当右边都比当前 A[i] 要大，那我们维护的单调递减栈就会不断出栈，不断出栈，直到栈为空为止，此时右边个数应该为 A.length-i（不用+1的原因是从 0 计数），那么这部分大佬设为 A.length 就很巧妙了，依旧清晰明了。
/**
* @param {number[]} A
* @return {number}
*/
var sumSubarrayMins = function (A) {
let mod = 1e9 + 7;
// 维护一个栈
let stack = [];
// 求以A[i]为最小值的子数组左边大于或等于自己的个数
let prev = [];
for (let i = 0; i < A.length; i++) {
while (stack.length && A[stack[stack.length - 1]] >= A[i]) stack.pop();
// 如果栈为空，即左边都比自己大，则返回i+1，否则返回i-栈顶元素（即保存的下标值）
prev[i] = stack.length ? i - stack[stack.length - 1] : i + 1;
stack.push(i);
}
stack = [];
// 求以A[i]为最小值的子数组右边大于自己的个数（没有等号是因为不会重复计算相等的值）
let nextv = [];
for (let i = A.length - 1; i >= 0; i--) {
while (stack.length && A[stack[stack.length - 1]] > A[i]) stack.pop();
// 如果栈为空，即右边都比自己大，则返回A.length-i，否则返回栈顶元素（即保存的下标值）-i
nextv[i] = stack.length ? stack[stack.length - 1] - i : A.length - i;
stack.push(i);
}
let sum = 0;
for (let i = 0; i < A.length; i++) {
// 以A[i] 为最小值的子数组的组合共有prev[i]*nextv[i]种情况，那么和的话乘以A[i]累加即可
sum += prev[i] * nextv[i] * A[i];
// 按题意，进行取模运算
sum %= mod;
}
return sum;
};
class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
int mod = 1e9 + 7;
stack<int> st;
vector<int> prev(A.size()), next(A.size());
for (int i = 0; i < A.size(); i++) {
while (!st.empty() && A[st.top()] >= A[i]) st.pop();
prev[i] = st.empty() ? i + 1 : i - st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = A.size() - 1; i >= 0; i--) {
while (!st.empty() && A[st.top()] > A[i]) st.pop();
next[i] = st.empty() ? A.size() - i : st.top() - i;
st.push(i);
}
int sum = 0;
for (int i = 0; i < A.size(); i++) {
sum += prev[i] * next[i] * A[i];
sum %= mod;
}
return sum;
}
};
class Solution {
public int sumSubarrayMins(int[] A) {
int mod = 1_000_000_007;
Stack<Integer> st = new Stack<>();
int[] prev = new int[A.length];
for (int i = 0; i < A.length; i++) {
while (!st.isEmpty() && A[st.peek()] >= A[i]) st.pop();
prev[i] = st.isEmpty() ? i + 1 : i - st.peek();
st.push(i);
}
while (!st.isEmpty()) st.pop();
int[] next = new int[A.length];
for (int i = A.length - 1; i >= 0; i--) {
while (!st.isEmpty() && A[st.peek()] > A[i]) st.pop();
next[i] = st.isEmpty() ? A.length - i : st.peek() - i;
st.push(i);
}
int sum = 0;
for (int i = 0; i < A.length; i++) {
sum += prev[i] * next[i] * A[i];
sum %= mod;
}
return sum;
}
}
class Solution:
def sumSubarrayMins(self, A: List[int]) -> int:
mod = 10 ** 9 + 7
stack = []
prev = [0] * len(A)
for i in range(len(A)):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
prev[i] = i + 1 if not stack else i - stack[-1]
stack.append(i)
stack = []
nextv = [0] * len(A)
for i in range(len(A) - 1, -1, -1):
while stack and A[stack[-1]] > A[i]:
stack.pop()
nextv[i] = len(A) - i if not stack else stack[-1] - i
stack.append(i)
res = 0
for i in range(len(A)):
res += prev[i] * nextv[i] * A[i]
res %= mod
return res
学如逆水行舟，不进则退