方法一： 单调栈（单调递增栈）
1. 对给定数组 A[ ] 中的每个元素 A[i] ，如果能 求出包含 arr [ i ] 并以 A[i] 为最小元素的所有子数组个数n[i]，
则元素 A[i] 对答案 ans 的贡献为n[i]* A[i] 。
2. 那么我们可以先求包含 A[i] 并以A[i]为最小元素的最长子数组，如果A[i]左边第一个小于A[i]的元素为A[left]，A[i]
右边第一个小于等于 A[i] 的元素为A[right]，则包含A[i] 并以A[i]为最小元素的最长子数组为A[left+1:right - 1]，满足以A[i]为
最小元素的所有子数组个数n[i] = (i-left)*(right-i)。
3. 我们用left[i]表示A[i]左边第一个小于A[i]元素的位置，用right[i]表示A[i]右边第一个小于等于A[i]元素的位置，left数组初始值为-1，
right数组初始值为len(A)，求解left和right可以用单调栈来实现。
注： 考虑到 以A[i]为最小元素的最长子数组中 以A[i] 最小值可能 出现多次，那么只取第一次出现的最小值。所以左边取小于，右边取小于等于。
时间复杂度O(N)
空间复杂度O(N)
1 class Solution { 2 public: 3 int sumSubarrayMins(vector<int>& arr) 4 { 5 const int BASE = 1e9 + 7; 6 stack<int> stk; 7 arr.push_back(0); // 哨兵，保证栈中所有元素都会被弹出计算 8 int len = arr.size(); 9 long res = 0; 10 for ( int i = 0; i < len; ++i ) 11 { 12 //维护一个严格单调递增的栈 13 while ( !stk.empty() && arr[i] <= arr[stk.top()] ) 14 { 15 int index = stk.top(); 16 stk.pop(); 17 int prev_index = -1; 18 if ( !stk.empty() ) prev_index = stk.top(); 19 int prev_count = index - prev_index ; // 数量m 20 int next_count = i - index ; // 数量n 21 long res_idx = long(arr[index]) * (prev_count ) * (next_count) % BASE; 22 res += res_idx; 23 res %= BASE; 24 } 25 stk.push(i); 26 } 27 return res; 28 } 29 };
类似题目:
方法二 dp 超时
1 class Solution { 2 public: 3 int sumSubarrayMins(vector<int>& arr) 4 { 5 const int len = arr.size(); 6 vector<vector<int>> dp(len,vector<int>(len,0)); 7 min_sum = 0; 8 for(int i = 0; i < len; ++i) 9 { 10 dp[i][i] = arr[i]; 11 min_sum += dp[i][i]; 12 if(i+1 < len) 13 { 14 dp[i][i+1] = std::min(arr[i],arr[i+1]); 15 min_sum += dp[i][i+1]; 16 } 17 } 18 for(int j = 2; j < len;++j) 19 { 20 for(int i = 0; i < j - 1;++i) 21 { 22 dp[i][j] = std::min(dp[i+1][j-1],min(arr[i],arr[j])); 23 min_sum += dp[i][j]; 24 } 25 } 26 return min_sum % (long long)(pow(10,9)+7); 27 } 28 private: 29 long long min_sum; 30 };
微软面试题： LeetCode 907. 子数组的最小值之和 middle 出现次数：1
原文：https://www.cnblogs.com/wangxf2019/p/14702163.html