← Static tasks

907. Sum of Subarray Minimums

leetcode medium

#array#csharp#leetcode#medium#stack#two-pointers

Task

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

Пример:

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

Output: 17

C# solution

matched/original
public class Solution {
    public int SumSubarrayMins(int[] arr) {
        const int MOD = 1_000_000_007;
        int n = arr.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && arr[stack.Peek()] > arr[i]) {
                stack.Pop();
            }
            left[i] = stack.Count == 0 ? i + 1 : i - stack.Peek();
            stack.Push(i);
        }
        stack.Clear();
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && arr[stack.Peek()] >= arr[i]) {
                stack.Pop();
            }
            right[i] = stack.Count == 0 ? n - i : stack.Peek() - i;
            stack.Push(i);
        }
        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long)arr[i] * left[i] * right[i]) % MOD;
        }
        return (int)result;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SumSubarrayMins(vector<int>& arr) {
        const int MOD = 1_000_000_007;
        int n = arr.size();
        vector<int>& left = new int[n];
        vector<int>& right = new int[n];
        stack<int> stack = new stack<int>();
        for (int i = 0; i < n; i++) {
            while (stack.size() > 0 && arr[stack.Peek()] > arr[i]) {
                stack.pop();
            }
            left[i] = stack.size() == 0 ? i + 1 : i - stack.Peek();
            stack.push(i);
        }
        stack.Clear();
        for (int i = n - 1; i >= 0; i--) {
            while (stack.size() > 0 && arr[stack.Peek()] >= arr[i]) {
                stack.pop();
            }
            right[i] = stack.size() == 0 ? n - i : stack.Peek() - i;
            stack.push(i);
        }
        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long)arr[i] * left[i] * right[i]) % MOD;
        }
        return (int)result;
    }
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int SumSubarrayMins(int[] arr) {
        const int MOD = 1_000_000_007;
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < n; i++) {
            while (stack.size() > 0 && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            left[i] = stack.size() == 0 ? i + 1 : i - stack.peek();
            stack.push(i);
        }
        stack.Clear();
        for (int i = n - 1; i >= 0; i--) {
            while (stack.size() > 0 && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            right[i] = stack.size() == 0 ? n - i : stack.peek() - i;
            stack.push(i);
        }
        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long)arr[i] * left[i] * right[i]) % MOD;
        }
        return (int)result;
    }
}

JavaScript solution

matched/original
var sumSubarrayMins = function(arr) {
    const MOD = 1e9 + 7;
    const n = arr.length;
    const left = new Array(n).fill(0);
    const right = new Array(n).fill(0);
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {
            stack.pop();
        }
        left[i] = stack.length ? i - stack[stack.length - 1] : i + 1;
        stack.push(i);
    }
    
    stack.length = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        right[i] = stack.length ? stack[stack.length - 1] - i : n - i;
        stack.push(i);
    }
    
    let result = 0;
    for (let i = 0; i < n; i++) {
        result = (result + arr[i] * left[i] * right[i]) % MOD;
    }
    
    return result;
};

Python solution

matched/original
def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    left = [0] * n
    right = [0] * n
    stack = []

    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        left[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

    stack = []

    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        right[i] = n - i if not stack else stack[-1] - i
        stack.append(i)

    result = sum(a * l * r for a, l, r in zip(arr, left, right)) % MOD
    return result

Go solution

matched/original
package main

func sumSubarrayMins(arr []int) int {
    const MOD = 1_000_000_007
    n := len(arr)
    left := make([]int, n)
    right := make([]int, n)
    stack := []int{}

    for i := 0; i < n; i++ {
        for len(stack) > 0 && arr[stack[len(stack)-1]] > arr[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            left[i] = i + 1
        } else {
            left[i] = i - stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    stack = []int{}

    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            right[i] = n - i
        } else {
            right[i] = stack[len(stack)-1] - i
        }
        stack = append(stack, i)
    }

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

    return result
}

Explanation

Algorithm

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

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

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

😎