907. Sum of Subarray Minimums

LeetCode medium оригинал: C# #array #csharp #leetcode #medium #stack #two-pointers

LeetCode Static

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

Пример:

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

Output: 17

C# решение

сопоставлено/оригинал

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++ решение

auto-draft, проверить перед отправкой

#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 решение

auto-draft, проверить перед отправкой

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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 решение

сопоставлено/оригинал

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
}

Algorithm

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

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

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

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.