leetcode 907. Sum of Subarray Minimums 子数组的最小值之和-内存100

Problem: 907. Sum of Subarray Minimums 子数组的最小值之和

内存100%，统计了每个数字的贡献，像 3 1 2 4, 3只贡献了1次，1贡献了 2 * 3 = 6 次，2贡献了2次，4贡献了1次

上面1的贡献次数，是统计左侧>=1的个数=2（3 1和1），统计右侧<=1的个数=3（1和1 2和1 2 4），

当出现相邻重复数字的时候，像3 3，只统计左侧==，共3个子数组（3， 3 3， 3）

Code

class Solution { public: const int modulo = 1e9 + 7; int sumSubarrayMins(vector<int>& arr) { int l, r, n = arr.size(); long long sum = 0; for(int i = 0; i < n; i++) { l = i - 1; r = i + 1; while(l >= 0 && arr[l] >= arr[i]) l--; while(r < n && arr[r] > arr[i]) r++; sum += ( ((long long)arr[i] * (long long)(i - l) * (long long)(r - i)) % modulo ); sum %= modulo; } return sum; } };

官方题解使用单调栈，求出了每个数字左右的长度，时间复杂度减少到O(n)

class Solution { public: const int modulo = 1e9 + 7; int sumSubarrayMins(vector<int>& arr) { int l, r, n = arr.size(); long long sum = 0; vector<int> stackmono; vector<int> left(n), right(n); for(int i = 0; i < n; i++) { while(stackmono.size() > 0 && arr[i] <= arr[stackmono.back()]) { stackmono.pop_back(); } left[i] = i - (stackmono.size()==0? -1 : stackmono.back()); stackmono.emplace_back(i); } stackmono.clear(); for(int i = n-1; i >= 0; i--) { while(stackmono.size() > 0 && arr[i] < arr[stackmono.back()]) { stackmono.pop_back(); } right[i] = (stackmono.size()==0? n : stackmono.back()) - i; stackmono.emplace_back(i); } for(int i = 0; i < n; i++) { sum = (sum + (long long)arr[i] * (long long)left[i] * (long long)right[i]) % modulo; } return sum; } };