📌 Задача leetcode. Sum of Subarray Minimums
Сложность: Средняя
Задача: Дан массив целых чисел, необходимо посчитать сумму минимумов подмассивов, ответ может быть большим, необходимо посчитать результат по модулю
Пример:
Ввод:
Вывод:
Примечание:
Подмассивы:
Решение:
Пишите свое решение в комментариях👇
Сложность: Средняя
Задача: Дан массив целых чисел, необходимо посчитать сумму минимумов подмассивов, ответ может быть большим, необходимо посчитать результат по модулю
10^9 + 7. Пример:
Ввод:
arr = [3,1,2,4]Вывод:
17Примечание:
Подмассивы:
[3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4], минимумы этих подмассивов: 3, 1, 2, 4, 1, 1, 2, 1, 1, 1, которые в сумме дают 17.Решение:
func sumSubarrayMins(arr []int) int {
out := 0
var st stack
st.push(-1) // setting left bound
for i := range arr {
for len(st) > 1 && arr[i] <= arr[st.peak()] {
idx := st.pop()
out += (i - idx) * (idx - st.peak()) * arr[idx]
}
st = append(st, i)
}
for len(st) > 1 {
idx := st.pop()
out += (len(arr) - idx) * (idx - st.peak()) * arr[idx]
}
return out % 1000000007
}
type stack []int
func (s *stack) push(v int) {
*s = append(*s, v)
}
func (s *stack) pop() int {
v := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return v
}
func (s *stack) empty() bool {
return len(*s) == 0
}
func (s *stack) peak() int {
v := (*s)[len(*s)-1]
return v
}
Пишите свое решение в комментариях👇