Задача: 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 {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> left(n), right(n);
        stack<int> st;

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && arr[st.top()] > arr[i]) {
                st.pop();
            }
            left[i] = st.empty() ? i + 1 : i - st.top();
            st.push(i);
        }

        while (!st.empty()) st.pop();

        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && arr[st.top()] >= arr[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n - i : st.top() - i;
            st.push(i);
        }

        long long result = 0;
        for (int i = 0; i < n; ++i) {
            result = (result + (long long)arr[i] * left[i] * right[i]) % MOD;
        }

        return result;
    }
};

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