✅ Решение задачи 20

Time: O(n)
Space: O(n)

📝 Идея
▫️Перебираем строку и записываем в стек скобку противоположную открытой, теперь если встретилась закрытая скобка, то если на вершине стека на не такая же скобка или он вообще пуст, значит последовательность неправильная
▫️В конце методом .isEmpty() проверяем, что в стеке не осталось открытых скобок

#solution20

✅ Решение задачи 22

Time: O(2^n)
Space: O(n)

📝 Идея
▫️Реализуем функцию backtrack для перебора всех вариантов правильных скобок
▫️Главным условием создания правильной скобочной последовательности является то, что текущее количество открытых скобок больше или равно количеству закрытых, то есть закрытая скобка никогда не будет добавляться раньше открытой. Отсюда два варианта:
1️⃣ Если количество открытых скобок меньше n добавляем "(" в curr
2️⃣ Если количество открытых скобок больше количества закрытых добавляем ")" в curr
Далее запускаем рекурсию, после удаляем последний элемент, чтобы проверить все варианты скобочной последовательности
▫️Базовый случай в данном алгоритме - количество закрытых скобок равно n

#solution22

🟡 Medium
739. Daily Temperatures

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Подсказка: задача на использование стека

15/200
#medium
#leetcode739

🟡 Medium
853. Car Fleet

Пример:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3

▪️Автомобили, стартующие c 10 (скорость 2) и 8 (скорость 4), образуют автопарк, встречающийся в 12
▪️Автомобиль, стартующий с 0 (скорость 1), не догоняет ни один другой автомобиль, поэтому он сам по себе является автопарком.
▪️Автомобили, стартующие с 5 (скорость 1) и 3 (скорость 3), образуют автопарк, встречающийся в точке 6 и двигаются со скоростью 1, пока не достигнут target

Подсказка: попробуйте отсортировать позиции машин

16/200
#medium
#leetcode853

✅ Решение задачи 739

Time: O(n)
Space: O(n)

📝 Идея
▫️Проходимся по всему массиву, на каждом шаге в цикле проверяя: если на вершине стека значение меньше текущего, то значит мы нашли нужный элемент и можно записывать в ответ разницу в днях
▫️В стек сохраняем все индексы температур

#solution739

✅ Решение задачи 853

Time: O(nlog(n))
Space: O(n)

📝 Идея
▫️Создаем двумерный массив pairs, куда складываем пары position-speed и сортируем его по позициям
▫️Так как машины не могут обгонять, а только упираться друг в друга - идем с конца массива, делая проверку:
- Если время прихода в target текущей машины меньше или равно следующей, значит она ее догонит и образуется автопарк, соответственно уменьшаем максимально возможное количество (то есть n)
- Иначе обновляем текущее время прихода машины для следующих проверок

#solution853

🟢 Easy
121. Best Time to Buy and Sell Stock

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 5

Input: prices = [7,6,4,3,1]
Output: 0

Подсказка: используйте подход sliding window для решения за O(n)

17/200
#easy
#leetcode121

🔴 Hard
84. Largest Rectangle in Histogram

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10

Подсказка: в каком случаем столбец может расширяться дальше и как можно сохранять индексы?

18/200
#hard
#leetcode84

✅ Решение задачи 121

Time: O(n)
Space: O(1)

📝 Идея
▫️Для максимальной выгоды нам необходим день день с минимальной ценой, поэтому используя подход sliding windows проходимся по массиву, обновляя день с минимальной ценой и считая максимальную выгоду, как разницу цен в текущем дне и минимальной ценой
▫️Если все цены будут идти по убыванию, соответственно разница всегда будет отрицательной и ответ будет 0

#solution121

✅ Решение задачи 84

Time: O(n)
Space: O(n)

📝 Идея
▫️Идя по массиву смотрим, если столбец на вершине стека больше, чем текущий столбец, значит этому столбцу некуда больше расширяться и можно считать максимальное значение
▫️В стек сохраняем текущий индекс
▫️В результате в стеке остается возрастающая последовательность, по которой нужно пройтись и также проверить на возможное максимальное значение
▫️-1 в начале стека нужна для обработки значения под индексом 0

#solution84

🟢 Easy
704. Binary Search

Пример:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

Подсказка: как быстро найти слово в словаре?

19/200
#easy
#leetcode704

🟡 Medium
74. Search a 2D Matrix

Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Подсказка: что должно быть в качестве указателей в бинарном поиске для этой задачи?

20/200
#medium
#leetcode74

✅ Решение задачи 704

Time: O(log(n))
Space: O(1)

📝 Идея
▫️Бинарный поиск заключается в отделении половины ненужных элементов после проверки, что середина текущего отрезка меньше или больше target
▫️Мы может так делать, только если массив отсортирован
▫️Вместо привычной записи mid = (l + r) / 2 - здесь другая, это нужно для того, чтобы избежать переполнения int

#solution704

✅ Решение задачи 74

Time: O(log(mn))
Space: O(1)

📝 Идея
▫️Устанавливаем один указатель на первую строку, второй на последний элемент в строке
▫️Так как матрица отсортирована:
- если текущий элемент меньше target - остается только увеличивать индекс строки, потому что мы уже находимся на максимальном элементе в этой строке
- если больше - остается только уменьшать индекс столбца, так как мы уже дошли до нужной строки и меньшие элементы находятся только слева

#solution74

🟡 Medium
875. Koko Eating Bananas

Пример:

Input: piles = [3,6,7,11], h = 8
Output: 4

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Подсказка: в каком диапазоне может находиться k, и как тогда можно применить бинарный поиск?

21/200
#medium
#leetcode875

🟡 Medium
153. Find Minimum in Rotated Sorted Array

Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: Исходный массив [1,2,3,4,5] был повернут 3 раза.

Input: nums = [11,13,15,17]
Output: 11
Explanation: Исходный массив [11,13,15,17] был повернут 4 раза.

Подсказка: какое условие выполняется для указателей left и right в отсортированном массиве?

22/200
#medium
#leetcode153

✅ Решение задачи 875

Time: O(nlog(m))
Space: O(1)

📝 Идея
▫️Значение k может лежать в диапозоне от 1 до максимума в этом массиве (больше не имеет смысла)
▫️Бинарным поиском ищем минимальное значение k, при котором количество часов будет равно заданному h

#solution875

✅ Решение задачи 153

Time: O(log(n))
Space: O(1)

📝 Идея
▫️В отсортированном массиве первый элемент всегда максимальный, поэтому необходимо найти такой указатель l на отрезке массива, чтобы выполнялось условие nums[l] <= nums[r]

#solution153

🟢 Easy
643. Maximum Average Subarray I

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Максимальное среднее значение равно (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12,75

Подсказка: используйте "скользящее окно" длиной k

23/200
#easy
#leetcode643

🟡 Medium
3. Longest Substring Without Repeating Characters

Пример:

Input: s = "abcabcbb"
Output: 3
Explanation: ответ: "abc" длиной 3.

Input: s = "pwwkew"
Output: 3
Explanation: ответ: "wke" длиной 3.

Подсказка: какая структура данных подойдет для решения и как можно использовать подход sliding window?

24/200
#medium
#leetcode3

✅ Решение задачи 643

Time: O(n)
Space: O(1)

📝 Идея
▫️Посчитаем сумму первых k элементов, затем в новом цикле начиная с индекса k ищем максимально возможную сумму, добавляя к текущей сумме следующий элемент и удаляя при этом элемент i - k, чтобы размер "окна" не менялся
▫️Возвращаем полученную максимальную сумму, деленную на k (умножение на 1.0 нужно, чтобы привести сумму к типу double)

#solution643