🟡 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

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

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

📝 Идея
▫️если set не содержит текущий символ, просто добавляем его и сравниваем длину текущего "окна" с максимумом
▫️если set содержит текущий символ, удаляем левую часть "окна", пока set содержит данный символ

#solution3

🟡 Medium
424. Longest Repeating Character Replacement

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Замените две буквы «A» на две буквы «B» или наоборот.

Подсказка: какое условие должно выполняться для текущего отрезка строки, чтобы он подходил под ответ?

25/200
#medium
#leetcode424