Сумма минимальных значений подмассивов
Источник: https://leetcode.com/problems/sum-of-subarray-minimums/
Дан массив целых числе arr, надо найти сумму минимумовmin(b), где b - это непрерывный подмассив массива arr. Поскольку ответ может быть очень большим, то его надо вернуть по модулю 109 + 7.
Пример 1:
Дано: 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.
Пример 2:
Дано: arr = [11,81,94,43,3] Результат: 444
Ограничения:
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104
Идея решения
Монотонный стек - это стек, в котором элементы идут в возрастающем порядке.
Часто в алгоритмах идею монотонного стека реализуют следующим кодом (С++):
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && in_stk.top() > A[i]){
in_stk.pop();
}
in_stk.push(A[i]);
}
Для чего полезен монотонный стек?
(1) найти предыдущий меньший элемент для любого элемента в векторе за время O(n):
- Например:
[3, 7, 8, 4]
Предыдущий меньший элемент для 7: 3.
Предыдущий меньший элемент для 8: 7.
Предыдущий меньший элемент для 4: 3.
Нет предыдущего меньшего элемента для 3.
Обозначим предыдущий меньший элемент, как PLE - Previous Less Element.
В алгоритмах, вместо того, чтобы помещать в стек сам элемент, помещают его индекс:
// previous_less[i] = j означает, что A[j] - это PLE для A[i].
// previous_less[i] = -1 означает, что нет PLE для A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
in_stk.pop();
}
previous_less[i] = in_stk.empty()? -1: in_stk.top();
in_stk.push(i);
}
- Например:
[3, 7, 8, 4]
Следующий меньший элемент для 8: 4.
Следующий меньший элемент для 7: 4.
Нет следующего меньшего элемента для 3 и 4.
Следующий меньий элемент обозначим, как NLE - Next Less Element.
Имплементация на С++:
// next_less[i] = j означает, что A[j] - это NLE для A[i].
// next_less[i] = -1 означает, что нет следующего меньшего элемента для A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
auto x = in_stk.top(); in_stk.pop();
next_less[x] = i;
}
in_stk.push(i);
}
Как мы используем монотонный стек для текущей задачи?
Рассмотрим элемент 3 в массиве:
[2, 9, 7, 8, 3, 4, 6, 1]
| |
PLE для 3 NLE для 3
После нахождения NLE и PLE of 3, мы можем подсчитать расстояние между 3 and 2(PLE) , и расстояние между 3 and 1(NLE). Расстояние - это количество элементов в исходном массиве между двумя заданными элементами массива.
В нашем примере, эти расстояния будут4 и 3 соответственно.
В скольких подмассивах 3 being - это минимальное значение?
Ответ: 4*3.
9 7 8 3
9 7 8 3 4
9 7 8 3 4 6
7 8 3
7 8 3 4
7 8 3 4 6
8 3
8 3 4
8 3 4 6
3
3 4
3 4 6
Как элемент 3 влияет на ответ?
Элемент умножается на количество подмассивов, где он минимальный элемент? 3*(4*3).
Как подсчитать финальный ответ?
Обозначим left[i] расстояние между элементомA[i]и его PLE.
Обозначим right[i] расстояние между элементом A[i]и его NLE.
Ответ нашей задачи считается по формуле:sum(A[i]*left[i]*right[i] )
Имплементация
class Solution {
public int sumSubarrayMins(int[] A) {
int len = A.length;
Stack<Integer> stack = new Stack<>();
// считаем left и right для каждого элемента исходного массива
int[] left = new int[len];
int[] right = new int[len];
// инициализируем заведомо ложными индексами,
// которые мы вытолкнем из массива при первой возможности
for(int i = 0; i < A.length; i++) {
left[i] = i + 1;
right[i] = len - i;
}
// считаем PLE
for(int i = 0; i < len; i++){
while(!stack.isEmpty() && A[stack.peek()] > A[i]) {
stack.pop();
}
left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
// считаем NLE
stack = new Stack<>();
for(int i = 0; i < len; i++){
while(!stack.isEmpty() && A[stack.peek()] > A[i]) {
right[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
// применяем формулу
long ans = 0;
long mod = (int)1e9 + 7;
for(int i = 0; i < len; i++) {
ans = (ans +(long) A[i] * left[i] * right[i]) % mod; // по модулю
}
return (int)ans;
}
}
Комментарии
Отправить комментарий