Сообщения

Показаны сообщения с ярлыком "Стек"

Накопитель дождевой воды

Изображение
Источник: https://leetcode.com/problems/trapping-rain-water/ Даны n неотрицательных чисел, которые кодируют неровную поверхность, состояющую из столбиков. Ширина каждого столбика = 1. Подсчитать, сколько дождевой воды можно накопить между столбиками.   Пример 1: Дано: height = [0,1,0,2,1,0,1,3,2,1,2,1] Результат: 6 Объяснение: Неровная поверхность, образуемая столбиками (черные квадраты) закодирована массивом [0,1,0,2,1,0,1,3,2,1,2,1]. Вода (голубые столбики) задерживается во впадинах паверхности. И обозначена голубыми квадратами. Всего у нас 6 голубых квадратов. Пример 2: Дано: height = [4,2,0,3,2,5] Результат: 9 Ограничения: n == height.length 1 <= n <= 2 * 10 4 0 <= height[i] <= 10 5 Идея решения Мы можем использовать стек, чтобы учитывать столбики поверхности, которые окружены другими столбиками - и значит, они могут быть покрыты водой. Сканируем массив и добавляем индекс элемента в стек, когда он меньше или равен элементу, соответствующему индексу в топе...

Сумма минимальных значений подмассивов

Источник: https://leetcode.com/problems/sum-of-subarray-minimums/ Дан массив целых числе arr, надо найти сумму минимумов min(b) , где b - это непрерывный подмассив массива arr . Поскольку ответ может быть очень большим, то его надо вернуть по модулю 10 9   + 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 * 10 4 1 <= arr[i] <= 3 * 10 4 Идея решения Монотонный стек - это стек, в котором элементы идут в возрастающем порядке. Часто в алгоритмах идею монотонного стека реализуют следующим кодом (С++): 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) найти предыдущи...

Эксклюзивное время исполнения функций

Изображение
Источник: https://leetcode.com/problems/exclusive-time-of-functions/ На однопотоково процессоре исполняется программа из n функций. У каждой функции есть уникальный ID между 0 и n-1. Вызовы функций хрнаятся в стеке: ID функции заносится в стек в начале исполнения функции и удаляется из него в конке исполнения функции. Функция, чей ID в верхушке стека - исполняющаяся в текущий момент функция. Каждый раз, когда функция начинается и заканчивается, мы пишем лог с ID, начало или конец исполнения, таймстемп. Дон список логов logs, где logs[i] предсталяет собой i-е сообщение лога в формате: "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что функция с ID=0 стартовала в момент времени, кjгда timestamp=3, "1:end:2" функция с ID=1 закончилась в момент времени timestamp=2.  Функиця может быть вызвана много раз, в том числе и рекурсивно. Эксклюзивное время фукнции - это сумма всех интервалов исполнения. Например, есл...