Задача: 907. Sum of Subarray Minimums
Сложность: medium

Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.

Пример:

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

👨‍💻 Алгоритм:

1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива.

2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным.

3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
    func sumSubarrayMins(_ arr: [Int]) -> Int {
        let MOD = 1_000_000_007
        let n = arr.count
        var left = [Int](repeating: 0, count: n)
        var right = [Int](repeating: 0, count: n)
        var stack = [Int]()
        
        for i in 0..<n {
            while !stack.isEmpty && arr[stack.last!] > arr[i] {
                stack.removeLast()
            }
            left[i] = stack.isEmpty ? i + 1 : i - stack.last!
            stack.append(i)
        }
        
        stack = []
        
        for i in stride(from: n - 1, through: 0, by: -1) {
            while !stack.isEmpty && arr[stack.last!] >= arr[i] {
                stack.removeLast()
            }
            right[i] = stack.isEmpty ? n - i : stack.last! - i
            stack.append(i)
        }
        
        var result = 0
        for i in 0..<n {
            result = (result + arr[i] * left[i] * right[i]) % MOD
        }
        
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний