Description (leetcode)

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [3,1,2,4]

Output: 17

Explanation:

Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].

Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.

Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]

Output: 444

Constraints:

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 3 * 10^4

submission

impl Solution {
    pub fn sum_subarray_mins(arr: Vec<i32>) -> i32 {
        let mut stack = Vec::with_capacity(arr.len());
        let mut dp = vec![0; arr.len() + 1];
        arr.iter()
            .enumerate()
            .rev()
            .fold(0, |sum, (idx, &val)| {
                while stack.pop_if(|&mut (_, _val)| _val >= val).is_some() {}
                let j = stack.last().map_or(arr.len(), |&(_idx, _val)| _idx);
                dp[idx] = (j - idx) as i32 * val + dp[j];
                stack.push((idx, val));
                (sum + dp[idx]) % 1_000_000_007
            })
    }
}