✅ Решение задачи 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

🟡 Medium
567. Permutation in String

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 содержит одну перестановку s1 ("ba").

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

26/200
#medium
#leetcode567

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

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

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

#solution424

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

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

📝 Идея
▫️Строка, которая является перестановкой другой строки имеет такое же количество символов, поэтому, перебирая вторую строку, сравниваем - если массивы строк count1 и count2 одинаковые, значит мы нашли нужную подстроку
▫️При этом следим, чтобы размер "окна" совпадал с размером строки s1, поэтому удаляем левый символ, если размер стал больше

#solution567