32 lines
766 B
C++
32 lines
766 B
C++
|
#include <vector>
|
||
|
|
|
||
|
|
class Solution {
|
||
|
|
static const int MOD = 1000000007;
|
||
|
|
|
||
|
|
public:
|
||
|
|
int sumSubarrayMins(const std::vector<int> &arr) {
|
||
|
|
long s = 0;
|
||
|
|
|
||
|
|
std::vector<int> stack;
|
||
|
|
for (auto i = 0; i <= static_cast<int>(arr.size()); ++i) {
|
||
|
|
while (!stack.empty() &&
|
||
|
|
(i == arr.size() || arr[stack.back()] >= arr[i])) {
|
||
|
|
int mid = stack.back();
|
||
|
|
stack.pop_back();
|
||
|
|
|
||
|
|
int l = stack.empty() ? -1 : stack.back();
|
||
|
|
int r = i;
|
||
|
|
|
||
|
|
long count = (mid - l) * (r - mid) % MOD;
|
||
|
|
|
||
|
|
s += (count * arr[mid]) % MOD;
|
||
|
|
s %= MOD;
|
||
|
|
}
|
||
|
|
|
||
|
|
stack.push_back(i);
|
||
|
|
}
|
||
|
|
|
||
|
|
return static_cast<int>(s);
|
||
|
|
}
|
||
|
|
};
|