problem:907. 子数组的最小值之和
思路:贡献法,可以求出每个数的左右两侧第一个比他的数,(相当于算出每个最小值对答案的贡献)在累加起来即可。
完整的思路: 灵神
Accode:
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
stack<int> sta;
int len = arr.size();
vector<int> right_larger(len,len),left(len,-1);
for(int i=0;i<len;i++){
while(sta.size() && arr[sta.top()]>arr[i]){
right_larger[sta.top()] = i;
sta.pop();
}
sta.push(i);
}
// 3 1 3 4 3+3=6
while(sta.size()) sta.pop();
for(int i=len-1;i>=0;i--){
while(sta.size() && arr[sta.top()]>=arr[i]){
left[sta.top()] = i;
sta.pop();
}
sta.push(i);
}
long long ans = 0;
int mod = 1e9+7;
for(int i=0;i<len;i++){
ans=ans+(long long)(i-left[i])*(right_larger[i]-i)*arr[i];
ans %=mod;
}
return ans;
}
};
时间复杂度:$o(n)$