blob: ee28cb9f242bf2f1c22e5e54bcb8d7001a2d9c8a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
use std::collections::VecDeque;
struct Solution;
impl Solution {
pub fn sum_subarray_mins(arr: Vec<i32>) -> i32 {
const MOD: i32 = 1e9 as i32 + 7;
let n: usize = arr.len();
let mut stk: VecDeque<isize> = {
let mut stk: VecDeque<isize> = VecDeque::with_capacity(n);
stk.push_back(-1);
stk
};
let mut ans: i32 = 0;
let mut dp: Vec<i32> = vec![0; n + 1];
for i in 0..n {
while let Some(&top) = stk.back() {
if top != -1 && arr[i] <= arr[top as usize] {
stk.pop_back();
} else {
break;
}
}
if let Some(&top) = stk.back() {
dp[i + 1] = (dp[top as usize + 1] + (i as i32 - top as i32) * arr[i]) % MOD;
}
stk.push_back(i as isize);
ans += dp[i + 1];
ans %= MOD;
}
ans
}
}
fn main() {
let arr = vec![3,1,2,4];
print!("{}", Solution::sum_subarray_mins(arr));
}
|