Сложность: medium
Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.
Пример:
Input: arr = [3,1,2,4]
Output: 17
👨💻 Алгоритм:
1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива.
2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным.
3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7.
😎 Решение:
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
Ставь 👍 и забирай 📚 Базу знаний