C ++中子数组最小值的总和
假设我们有一个整数数组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。
为了解决这个问题，我们将遵循以下步骤-
m：=1x10^9+7
定义两个方法，add()取a，b并返回（amodm+bmodm）modm，mul()取a，b并返回（amodm*bmodm）modm
main方法将获取数组A，定义堆栈st，并设置n：=数组A的大小
在大小为n的左侧定义两个数组，并以-1填充，在大小为n的右侧，定义另一个数组，以n填充
设置ans：=0
对于i，范围为0至n–1
当st不为空且A[stacktop]>=A[i]时，从st中删除
如果st不为空，则设置left[i]：=st的顶部
将我插入st
如果st不为空，则删除st
当我在n–1范围内下降到0
当st不为空且A[stacktop]>=A[i]时，从st中删除
如果st不为空，则设置right[i]：=st的顶部
将我插入st
对于i，范围为0至n–1
leftBound：=i–左[i]+1，rightBound：=右[i]–1–i
contri：=1+leftBound+rightBound+（leftBound*rightBound）
ans：=add（ans和mul（contri，A[i]））
返回ans
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return (a % MOD + b % MOD) % MOD;
}
lli mul(lli a, lli b){
return (a % MOD * b % MOD) % MOD;
}
int sumSubarrayMins(vector<int>& A) {
stack <int> st;
int n = A.size();
vector <int> left(n, -1);
vector <int> right(n, n);
int ans = 0;
for(int i = 0; i < n; i++){
while(!st.empty() && A[st.top()] >= A[i]){
st.pop();
}
if(!st.empty())left[i] = st.top();
st.push(i);
}
while(!st.empty())st.pop();
for(int i = n - 1; i >= 0; i--){
while(!st.empty() && A[st.top()] > A[i]){
st.pop();
}
if(!st.empty())right[i] = st.top();
st.push(i);
}
for(int i = 0; i < n; i++){
int leftBound = i - (left[i] + 1);
int rightBound = (right[i] - 1) - i;
int contri = 1 + leftBound + rightBound + (leftBound * rightBound);
ans = add(ans, mul(contri, A[i]));
}
return ans;
}
};
main(){
vector<int> v = {3,1,2,4};
Solution ob;
cout << (ob.sumSubarrayMins(v));
}输入值
[3,1,2,4]
输出结果
17