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：= 1 x 10 ^ 9 + 7

• 定义两个方法，add()取a，b并返回（a mod m + b mod m）mod m，mul()取a，b并返回（a mod m * b mod m）mod m

• main方法将获取数组A，定义堆栈st，并设置n：=数组A的大小

• 在大小为n的左侧定义两个数组，并以-1填充，在大小为n的右侧，定义另一个数组，以n填充

• 设置ans：= 0

• 对于i，范围为0至n – 1

• 当st不为空且A [stack top]> = A [i]时，从st中删除

• 如果st不为空，则设置left [i]：= st的顶部

• 将我插入st

• 如果st不为空，则删除st

• 当我在n – 1范围内下降到0

• 当st不为空且A [stack top]> = 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