LeetCode 907. 子数组的最小值之和
原题链接
中等
作者:
我是java同学
,
2023-10-09 16:36:31
,
所有人可见
,
阅读 50
class Solution {
public:
int sumSubarrayMins(vector<int>& w) {
int n = w.size();
vector<int> l(n), r(n);
stack<int> stk;
// 及时去掉无用数据
// 保证栈中数据有序
for (int i = 0; i < n; i ++ ) {
//如果一个区间里有两个相同的数,默认左边的更小
//从右往左只能把大于的删掉
while (stk.size() && w[stk.top()] > w[i]) stk.pop();
if (stk.empty()) l[i] = -1;
else l[i] = stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; i -- ) {
while (stk.size() && w[stk.top()] >= w[i]) stk.pop();
if (stk.empty()) r[i] = n;
else r[i] = stk.top();
stk.push(i);
}
typedef long long LL;
const int MOD = 1e9 + 7;
int res = 0;
for (int i = 0; i < n; i ++ )
res = (res + (LL)w[i] * (i - l[i]) * (r[i] - i)) % MOD;
return res;
}
};
%%%