微软面试题： LeetCode 907. 子数组的最小值之和 middle 出现次数：1

方法一：单调栈（单调递增栈）

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] 最小值可能出现多次，那么只取第一次出现的最小值。所以左边取小于，右边取小于等于。

时间复杂度

空间复杂度

 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 };