Подготовка к собеседованию в Google - Хитрая задача на Стек
Вставка
- Опубліковано 22 чер 2020
- Разбираем довольно сложную алгоритмическую задачу по программированию с применением стека. Ее могут спросить на собеседовании в Google, Amazon и Facebook.
Эта задача на LeetCode: leetcode.com/problems/daily-t...
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Вы прекрасно объясняете алгоритмы и структуры данных. Это очень большая редкость. Надеюсь что Вы вернётесь к ведению канала и будете продолжать просвещать начинающих it-специалистов.
Это не только для начинающих. :-))
Лучшее объяснение алгоритмов, нет слов, просто потрясающще!!!
Александр, очень нравится как вы объясняет материал. Спокойно и понятно. Спасибо.
Парень прирожденный препод! :) Очень доходчиво.
Интересная задача и очень понятное объяснение решения! Спасибо!
С таким кайфом вообще смотрю, спасибо огромное
Спасибо за пример и хорошее объяснение! 👍
Если не ошибаюсь, то стек тут не нужен, проблему можно решить за это же время без дополнительной памяти:
vector arr = {13, 12, 15, 11, 9 , 12, 16};
vector res;
res.resize(arr.size(), 0);
for(int i = res.size() - 2; i >= 0; --i) {
int j = i + 1;
while(res[j] != 0 && arr[j] arr[i]) res[i] = j - i;
}
Не ошибаешься, скрипач не нужен.
Что-то подсказывает, что ты прав, и сложность в твоем случае линейная, несмотря на то, что здесь цикл в цикле, и while иногда выполняется несколько раз. Можешь сказать, так ли это?
@@bohdansolonenko6554 да, теперь понял. Действительно, количество прыжков не больше, чем количество stack.pop() из реализации в видео и сложность не возрастает. Красиво, спасибо
Да, круто)
Линейное время неочевидно. В варианте со стеком линейное время доказывается доказывается через работу со стеком:
- В итерации цикла добавляется 1 элемент, и рассматривается [1 + количество удаляемых элементов].
- За время работы всего алгоритма каждый элемент удаляется один раз.
- Итого линейное количество итераций и линейное количество операций со стеком за весь алгоритм
Здесь тоже нужно как-то доказывать что res[i] рассматривается константное количество раз.
Можно идти по списку и в прямом порядке:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = [] # [(i1, t1), (i2, t2), ...]
result = [0] * len(temperatures)
for i, t in enumerate(temperatures):
while stack and stack[-1][1] < t: # stack[-1] means the last element
prev_i = stack.pop()[0]
result[prev_i] = i - prev_i
stack.append((i, t))
return result
Спасибо за видео, понятно объясняете
Решение со Stack прошло проверку. Спасибо за видео! лайк и подписка
Очень хорошее объяснение и залача, спасибо
Отличное видео, жаль что нет новых.
Классное объяснение!
Хорошее решение. Нет необходимости хранить в стеке значения температур, достаточно класть туда только индексы:
public int[] warmDays(int[] days) {
result = new int[days.length];
Stack stack = new Stack();
for(int day = days.length-1; day >= 0; day--) {
while (!stack.isEmpty() && days[stack.peek()]
Постоянно дергать базу чтобы из индекса вытащить температуру может быть тоже плохо
Интересная опция! На сложность (О) не влияет, но может быть принципиальным если значение не просто цифра, а сложный тяжелый объект.
@@by0uki это алгоритмическая задача, здесь не идет речь о работе с базой, данные находятся в памяти. Если хранить в стеке только индесы, то памяти потребуется в два раза меньше, а скорость не изменится
Отличное объяснение! У меня сначала появилась идея просто отсортировать массив по убыванию с сохранением индексов и потом бежать по нему и выделять в подмассив длинны n ответы по индексу элемента в подмассиве, но ваш вариант определенно лучше во всех случаях)
Спасибо большое бро! Канал топовый!
Позитивная подача и интересный материал !
Спасибо, хорошее решение. Сам решал так же со стеком, однако массив проходил в прямом порядке. Как по мне так короче и проще для понимания, при аналогичной сложности по времени и памяти:
def weather(arr):
stk = [] # ( temperature, i )
res = [0] * len(arr)
for i, cur in enumerate(arr):
while stk and stk[-1][0] < cur:
_, ix = stk.pop()
res[ix] = i - ix
stk.append((cur, i))
return res
import random
import time
l = [random.randint(-40, 40) for _ in range(1000000)]
s = time.time()
r = weather(l)
t = round((time.time() - s)*1000, 3)
print(r, t, sep="
")
Я Андрей и я работаю кассиром в Пятерочке. Надо начинать не с последнего элемента а предпоследнего так как у последнего всегда будет 0.
Если в вашем языке нет стека - как к примеру в дарте то можете использовать такое решение:
Solution {
List dailyTemperatures(List temperatures) {
final List result = List.filled(temperatures.length, 0);
for (var i = temperatures.length - 2; i >= 0; i--) {
if (temperatures[i] < temperatures[i + 1]) {
result[i] = 1;
} else {
int j = i + 1;
while (result[j] != 0) {
j = j + result[j];
if (temperatures[i] < temperatures[j]) {
result[i] = j - i;
break;
}
}
}
}
return result;
}
}
Какой же ты крутой бро, лайк тебе)))
Очень крутая подача, автору респект!
Array.prototype.last = function() {return this[this.length - 1] ?? undefined}
let n = [13, 12, 15, 11, 9, 12, 16]
let stack = []
let answer = new Array(n.length).fill(0)
n.forEach((el, idx) => {
while (n[stack.last()] < el) {
let val = stack.pop()
answer[val] = idx - val
}
stack.push(idx)
})
console.log(answer)
У меня получилось такое решение (JS), до того как посмотрел разбор. Спасибо большое за задачу :)
Интересная задача. Спасибо вам за такое хорошее и понятное объяснение!)
Красава вапще, я не могу просто над тобой, лайк, подписка, и high recommended
Прекрасное лаконичное изложение материала, спасибо. В стек не обязательно сохранять значения, достаточно просто индексы. По ним в исходном массиве находим значение.
Кстати, да. LinkedList - тоже вариант
хорошее дополнение 👍👍
Читать список не последовательно довольно тяжело для процессора (почитайте про кеширование). Так что лучше все же сохранять значения также.
@@MaratAshrafzianov 1.Если все данные записаны в кеш процессора, то разницы никакой.
2. Размер данных меньше минимум в 2 раза. Неизвестно, что станет бутылочным горлышком в дальнейшем и какие данные поместятся в кеш полностью.
3. При текущем алгоритме данные тоже пишутся не последовательно (попеременное обращение в разные области).
4. Экономия на спичках, коим является учитывание кэш процессора, является самым затруднительным и с минимальным приростом по производительности действием. Тем более, когда пример дан на Java
Понятно и без воды, лайк 👍
С временной сложностью не совсем очевидно, но именно взаимодействий со стеком (вставок и удалений) в худшем случае
Спасибо
Тут на помощь придет ещё одно наблюдение: на каждом шаге мы вставляем ровно один элемент и удаляем ноль или более. Поскольку мы всего вставляем максимум n элементов, то и удаляем мы всего максимум n элементов. Операции со стеком занимают время O(1), так что тут все достаточно просто: общая амортизарованная сложность по времени O(n). И по памяти тоже O(n).
Спасибо. Всё шикарно
int main() {
std::vector t = {13, 12, 15, 11, 9, 12, 16};
std::vector days = {};
int j = 0;
int i = 1;
while (days.size() - 1 != t.size() - 2) {
if (t[j] < t[i]) {
days.push_back(i - j);
j++;
i = j;
}
else i++;
}
days.push_back(0);
for (int c : days) std::cout
Крутое решение! 💪
Не смотрите это видео зимой! По ролика мозг перед числами рисовал мне минус. Поэтому у меня возникал постоянный вопрос: "Какого хрена 15, теплее чем 9. - 9 это же теплая зимняя погода, а - 15 это ближе к дубаку)))
Изящно! :)
Спасибо 🔥
Круть, спасибо)
Спасибо!
Отличный материал, шикарная подача, спасибо! Только насчёт удобного класса для 2-х значений, есть Point, не подходит?)
Чем второй способ с созданием, добавлением и удалением объекта в стекле лучше первого? Не разобрали такты процессора и работу с кэшем.
Видео про Google интервью - ua-cam.com/video/1EFwLkbiTng/v-deo.html
Жду Ваших комментариев.
Like и Subscribe приветствуются!
Стек не дает преимуществ. Кажется вроде он по памяти оптимизирован, но можно исполбзовать массив ответов и массив индексов следующего теплого дня. Да, массив индексов будет как массив ответов по длине, но у тебя нет лишней коллекции чтобы хранить температуры дней.
Хотя ладно, пока писал понял, что если исходный массив огромный, а мы ожидаем, что стек по ходу программы будет маленький, то выигрышь есть. А мои предыдущие размышления имеют вес только для вырожденного случая. Ты прав
Можно не создавать ещё коллекцию по хранению температур, можно обойтись самой высокой, чтобы потом перепрыгивать по элементам. Не особо хотел подробно описывать, может некоторым захочется самому подумать.
Я смотрю, многие пишут, что сложность не поменялась и всё ещё O(n^2). Нет, сложность будет O(n), потому что для каждого элемента мы выполняем максимум 3 операции: проходим по нему в массиве, добавляем в стек и удаляем его в из него. Рассмотрим на примере в видео.
13 12 15 11 9 12 16
Стек: пуст
1. Находим 16 в массиве.
2. Добавляем 16 в стек.
Стек: 16
3. Находим 12 в массиве.
4. Добавляем 12 в стек.
Стек: 12 16
5. Находим 9 в массиве.
6. Добавляем 9 в стек.
Стек: 9 12 16
7. Находим 11 в массиве.
8. Удаляем 9 из стека.
9. Добавляем 11 в стек
Стек: 11 12 16
10. Находим 15 в массиве.
11. Удаляем 11 из стека.
12. Удаляем 12 из стека.
13. Добавляем 15 в стек.
Стек: 15 16
14. Находим 12 в массиве.
15. Добавляем 12 в стек.
Стек: 12 15 16
16. Находим 13 в массиве.
17. Удаляем 12 из стека.
18. Добавляем 13 в стек.
Можно пронаблюдать, что с одним числом делается максимум 3 операции. Вообще, операций может быть немного больше, ведь мы можем какие переменные ещё подключать и тд, но суть в том, что из конечное, небольшое и с фиксированным максимумом количество.
Мне еще помогает понять сложность тот факт, что ни один элемент массива не попадет в стек более одного раза, а значит внутренний цикл while В СУММЕ будет выполняться O(n) раз.
У тебя ещё есть прогонка в стеке. А стек у тебя может по размеру быть как массив. И что бы найти в стеке нужный ты по факту получаешь O(n*n). Сложность же считается для алгоритма, а не для определённого решения. По этому O(n*n/2) тут
@@lawamoril прогонки не будет каждый раз, а максимум один раз, после чего элементы удалятся. Поэтому О(n).
Чтобы другим способом понять можно на примере рассмотреть крайние примеры "6 1 2 3 4 5" и "5 4 3 2 1 6" и увидеть, как красиво работает в обоих случаях стек. В то время как в 2 примере решение без стека, с циклом, будет выполняться за O(n^2) ((если про количество итераций, то (n*n/2), но 1/2 в O нотации опускаем).
@@lawamoril амортизированно по всем шагам мы удаляем из стека максимум n элементов, добавляем всегда n элементов. Не будет квадратичной сложности.
@@KirillFrolov77 Амортизированно == суммарно?
Можно сделать еще проще:
Не сохранять индексы. А кол-во суток через которое будет более теплый день будет показывать количество удалений элементов из стека + 1
На первый взгляд ваше утверждение кажется логичным, но на видео контрпример для самого левого элемента = 13. Кол-во удалений из стека на этом этапе явно больше двух
Еще не просмотрел видео, только прослушал условие и начал думать, а тут на глаза попалось название... Зачем же так сразу все палить :)
Не совсем понял второй ответ, возможно потому что далек от програмирования.
Разве для 4 элемента массива (9) следующим большим не будет 5элемент (12) ? Просто исходя из полученной информации в стеке на 4 элемент соответственно выдаст нижний элемент (16)?
И если первый элемент массива будет наибольшим, что мы получим на выходе? Не заметил проверку на это.
Да, правильно, для 4-ого элемента ответом будет 5-ый элемент и алгоритм из ролика так и считает. Когда мы доходим до этого самого 4-ого элемента мы уже прошли 5-ый и 6-ой, поэтому наш стек будет выглядеть так: 12(5), 16(6). А начинаем мы проходить по нему с вершины, то есть с 12, и поскольку сразу натыкаемся на число больше 9-ти, берём его ответом. Таким образом для 4-ого элемента ответом будет 5-ый.
@@kostya_superovotes8610 Спасибо!
Теперь понял.
Думал сперва полностью формируется стек для всего массива, а потом осуществляется перебор.
А вы в тактах процессора считали, что дороже циклы в кэше проца x86_64 крутить или стек городить с new + delete. Вот это как раз и есть разница в ява программистах и тех, кто на ассемблере работать умеет.
Разница инженера и кодера в том что инженер понимает что происходит при n -> стемящихся к большим числам.
@@serged5689 "Я это сделал не в интересах истины, а в интересах правды" (с)
Вы чего этим сказать то хоть хотели по разбору конкретно этого прикладного кейса?
А что произойдет в случае, если у нас день среди недели был самым жарким? Как будто бы этот нюанс не обработан в решении. Не знаю, как в джаве это будет выглядеть. Джаваскрипт бы выбросил ошибку
Но за объяснение спасибо большое
Мое персональное мнение, что ожидать решение такого типа - это против правил. Если для формулирования оптимального алгоритма надо знать приемчики - то такое интервью не дает вам никакой полезной информации. Ну или вернее, если человек знает это решение - то это подтверждение того факта, что он готовился, а не того, что он чего-то там умеет сам. В Amazon'е это бы классифицировали как trick question и в обсуждении не зачли бы. А интервьюеру сказали бы, чтобы он больше этот вопрос не использовал.
Что касается самого подхода, не сказаны главные слова. Надо сказать, что, мол, обратим внимание, что в любой момент времени нас интересуют ИСКЛЮЧИТЕЛЬНО дни справа, в которые температура была ВЫШЕ температуры текущего рассматриваемого дня. Поэтому все температуры, которые мы уже встретили справа и они ниже, можно смело выкидывать из рассмотрения, в любом случае расстояние от любой более низкой температуры слева до текущей будет короче, чем до любой более низкой температуры справа.
Вот именно из этого наблюдения следует оптимальное решение, а вовсе не из переборного решения. Использвать стек или нет - решение наживное, linked list тоже пойдет, там все операции с головой списка тоже O(1), как рту стека
Это не просто стек, это возрастающий монотонный стек (increasing monotonic stack), в котором значения только увеличиваются. И зачем отдельный класс для хранения так же не понятно, можно хранить элементы стека в формате массива [value, index].
Я бы загнал в бинарное дерево с сохранением индекса. Тогда для ответа нужно просто пройти по дереву в глубину в режиме inOrder.
И для каждого значения посчитать разницу с предыдущим индексом.
Тогда будет O(nlogn) + бинар дерево писать
Само создание дерева уже O(n*log(n)). И это мы ещё решать не начали. :-))
Я что-то не понял условие задачи - ведь для каждого дня в данном примере самая высокая температура будет последняя, почему для пнонедельника будет другой день?
Перечитал условие в другом месте, более понятно.
Нужно найти день после выбранного дня, температура которого превышает температуру выбранного дня.
Объясните плиз, почему в первом случае сложность считается как О(n^2). больше похоже на О(n^2 / 2). Из примера в видео с n = 7 получаем, что мы в худшем случае пройдем по массиву 6+5+4+3+2+1 = 21 раз, или тут деление на 2 это как константа и потому отбрасывается?
Константы выностяся за нотацию, да
Если в стеке нет элементов, в массив ответов нужно записать 0, а то в твоем тесткейсе, как я понимаю, последний день, ровно как и день с максимальной температурой, не обрабатывается никак.
Однако это не так уж и сложно обрабатывается, здесь важнее алгоритмика нежели полнота
массив ответов - это массив маленьких интов, что значит по умолчанию они все 0 и нет необходимости этот 0 еще раз проставлять.
Массив примитивов (например, int[]) в Java инициализируется значениями 0. Поэтому массив уже заполнен элементами, равными 0.
@@gandibaat3637 а при чем тут джава? это алгоритмическая задача
@@projeqt9243 претензии-то к конкретной реализации. А пример в видео написан на Java. Я и объясняю, почему принудительно писать в массив ответов нули не нужно.
Ох блин, я несколько дней думал над задачей, решение сам придумал, но двигался слева направо и код получился куда менее лаконичным (на С++). На leetcode по сложности тоже прошел тесты.
Все замечательно, только маленький диссонанс: с одной стороны собеседование в Гугл, а с другой стороны объясняем что такое стек.
Большая дорога начинается с первого шага. :)
вот блин, в названии видео был ответ, а я уже думал о сортировке с сохранением индексов и прочие усложнения
не правильно использовать "свойства" length, во втором параметре цикла for (let a = 0; a < t.length; a++)
потому что в таком случае каждый следующий шаг цикла будет каждый раз тратить время на определение t.length.
более быстрее будет сразу задать в первом параметре for (let a = 0, b = t.length; a < b; a++)
неправильно писать тяжелочитаемый код, выигрыш в производительности проигрыш в производительности очень незначителен, но код становится заметно легче для восприятия
@@cringoulique Вообще-то во многих крупных корпорациях выигрыш в производительности как раз таки очень значителен и является самым важным фактором, даже если код становится тяжелочитаемый. Потому что пользователи куда важнее чем программисты читающие код. Именно поэтому выигрыш в производительности очень даже значителен не смотря на тяжелочитаемый код. Особенно когда речь идёт о гиганстких обработок данных.
Да и к тому же, с какой стати код становится тяжелочитаемый ?? Изначально я привёл шапку цикла из примера видео, в нём 34 символа. Дополнение кода изменяет длину шапки всего до 37 символов. С какой стати такая разница превращает код в тяжелочитаемый, если само содержимое цикла не меняется.
💪👍
вот более эффективный алгоритм (быстрее примерно в 10-17 раз), без (явного) использования стека:
static int[] temperature(int[] t) {
int[] answer = new int[t.length];
for (int i = t.length - 1, head = -1; i >= 0; i--) {
while (-1 != head && t[head]
блин, я тоже сразу решил идти с конца. но так как вообще не работал со стеком. не подумал про него. а подумал про обычный массив🤔
Сильно зависит от условий, конечно. Почему-то снова оценка О() построена на том, что работа со стеком - бесплатная. Причем как удаление / добавление элементов, так и поиск нужного числа в стеке - внезапно бесплатный?! как это так? Это же совершенно не соответствует действительности! Оценка О(n) явно неправильная. В зависимости от везения (т.е. от исходных данных) вычислительная сложность решения со стеком будет на промежутке O(n)....O (n2). И это если не учитывать добавление / удаление в стеке, которое, повторюсь, совершенно не бесплатное.
Однако если последовательность дней ну оочень длинная и температура ходит "туда-сюда" - то выигрыш в решении со стеком будет, это да.
Для меня было проще обратное решение: проходить массив слева направо, добавлять в стэк кортеж: (температура + индекс) , и до этого вынимать из стека все показатели с температурой меньше, чем текущая и записывать в результат разность их индексов.
9:29 как нет?? почему бы не использовать мапы???
чувствую как становлюсь умнее...🤗
Почему так мало видосов? Мне кажется, надо заняться каналом и запилить новые алгоритмы.
Здорово, но зачем стек, если в массиве answer уже хранятся отностительные данные об индексах отработанных элементов?
Вроде можно вообще без стека
+
Интересно, почему вместо прямолинейного решения с проходом слева направо выбрано по сути эквивалентное с проходом справа налево :)
Если ты идешь слева направо и хочешь решить задачу за один проход - ты ничего не знаешь о будущих температурах, соответственно ничего не знаешь о расстоянии до ближайшего дня, когда будет теплее.
Если бы условие стояло "найти количество дней до дня в прошлом, когда было теплее", тогда бы можно было пройти слева направо и нельзя - справа налево.
@@gandibaat3637
def f(t_list, default=None):
ans = [default] * len(t_list)
stack = [0]
for i in range(1, len(t_list)):
cur_t = t_list[i]
last_t = t_list[stack[-1]]
while cur_t > last_t:
last_i = stack.pop()
ans[last_i] = i - last_i
if not stack:
break
last_t = t_list[stack[-1]]
stack.append(i)
return ans
@@Avorthoren справедливо и вроде работает на первый взгляд. Справа налево логичнее и проще для понимания как-то, на мой взгляд - считаем ответ для дня в массиве в тот момент, когда проходим по нему
@@gandibaat3637 Ну такое :) Вроде не менее логично пройти элемент, и, когда дойдём до элемента с большей температурой, вычислить ответ для исходного :)
@@gandibaat3637 Справа налево можно вообще без стека решить, просто использовать инфу о уже пройденных днях.
Так и не понял зачем стек когда можно хранить 1 число (последнее добавленное в стек), а его ответ укажет где находиться следующее «в стеке»
Потому что возможна ситуация при которой данные только последнего значения не будут достаточными для правильного ответа. Например, если у нас в стеке числа (9, 12, 16) , то для случаев нового дня с температурой 11 и 14 будут разные ответы, которые не получить только из последнего ответа для 9, нужен именно стек всех предыдущих значений.
@@serafim4372 да, но в примере у 9 тоже посчитано расстояние, на которое сразу можно перейти дальше и тд. Т е работать будет как в стеке, но без доп структуры, тк можно считать, что каждый элемент имеет ссылку на следующий в "стеке". и нам достаточно помнить индекс "верхушки"
"Поскольку каждый день мы можем добавить и удалить лишь 1 раз, то сложность O(n)."
Когда мы доходим до дня 2 с темп 15, то мы добавляем 1 раз, но удаляем 2 раза (удаляем день 3 и день 5). Или я что-то путаю? Кто-то может объяснить, пожалуйста, почему сложность O(n), даже в случае, когда мы имеем 100000 элементов и доходим до 0-ого элемента, который имеет, допустим, самую высокую температуру и в худшем случае мы вынуждены проходится обратно по всему стеку и удалять все дни по очереди до 100000-ого элемента?
Имеется в виду, что каждое число из массива может в худшем случае один раз попасть в стек и один раз из него удалиться. Получается максимум 2*N операций. Если мы в конце удалили 100000 элементов, это значит, что мы до этого ни разу ничего не удалили и 100000 раз добавили. Получается, мы сделали для 99999 чисел по одному добавлению и для одного последнего числа 100000 удалений. Всего как раз 2*N.
@@chichkan87 спасибо большое 🙏🏼
Собрался читать «Грокаем алгоритмы». Про О большое теперь что-то знаю :)
и в каком месте второго решения мы в ответы 0 кладем для 16?
А это уже тест на внимательность :) Вы приняты в Гугол :D
Массив изначально 0 заполнен в джаве
Если несложно, объясните пжста по первой части: при решении с двумя циклами получается, что в решение попадают значения из массива большие по условию, но перебор каждый раз начинается с начала массива, ответы попадают неверные
Перебор начинается не с начала массива, а с элемента на котором мы находимся +1
Ответы попадают верные, однако мы лишний раз проходимся по элементам которые не могут нам подойти
Во втором случае мы эти элементы убираем
@@user-bl2zl6jf2q спасибо)
@@user-bl2zl6jf2q всеравно не получается( я решаю в питоне, запускаю два цикла первый с перебором по значениям, второй с перебором по индексам. Индексы являются решением, но невсегда верны( т.к. каждый раз перебор начинается с начала списка. Помогетп пжста, уже две недели пытаюсь решить, и бросить не могу((
Но ведь можно использовать рекусию, или я заблуждаюсь? Просто тогда получается что Оn = (n-1)*n/2. Но я в это мне уверен...
Сложность будет O(n), потому что для каждого элемента мы выполняем максимум 3 операции: проходим по нему в массиве, добавляем в стек и удаляем его в из него. Рассмотрим на примере в видео.
13 12 15 11 9 12 16
Стек: пуст
1. Находим 16 в массиве.
2. Добавляем 16 в стек.
Стек: 16
3. Находим 12 в массиве.
4. Добавляем 12 в стек.
Стек: 12 16
5. Находим 9 в массиве.
6. Добавляем 9 в стек.
Стек: 9 12 16
7. Находим 11 в массиве.
8. Удаляем 9 из стека.
9. Добавляем 11 в стек
Стек: 11 12 16
10. Находим 15 в массиве.
11. Удаляем 11 из стека.
12. Удаляем 12 из стека.
13. Добавляем 15 в стек.
Стек: 15 16
14. Находим 12 в массиве.
15. Добавляем 12 в стек.
Стек: 12 15 16
16. Находим 13 в массиве.
17. Удаляем 12 из стека.
18. Добавляем 13 в стек.
Можно пронаблюдать, что с одним числом делается максимум 3 операции. Вообще, операций может быть немного больше, ведь мы можем какие переменные ещё подключать и тд, но суть в том, что из конечное, небольшое и с фиксированным максимумом количество.
На практике, решение с рекурсией работает быстрее
class Solution {
public int[] dailyTemperatures(int[] days) {
int day = 0;
do {
int dist = daysTraverse(days, day);
day += dist;
} while(day < days.length-1 && day > 0);
days[days.length-1] = 0;
return days;
}
public int daysTraverse(int[] days, int day) {
if(day == days.length - 1) {
return 0;
}
int next = day + 1;
int totalDist = 1;
while(days[day] >= days[next]) {
int dist = daysTraverse(days, next);
totalDist+=dist;
next += dist;
if(dist == 0) {
days[day] = 0;
return totalDist;
}
}
days[day] = totalDist;
return totalDist;
}
}
@@powerhead Сорри за вопрос старому сообщению, но рекурсия - это же тот же стек, только в него ложат не наши данные а текущее состояние системы. Как оно может быть быстрее? Кто знает?
На уникальных значениях температур оба алгоритма отрабатывают одинаково. Но пропустите через них массивы с неуникальными значениями - результаты кого-то могут удивить. А так тема интересная, объяснено замечательно. Спасибо Саша!
Ничего подобного, совершенно не одинаково. Возьмите массив уникальных температур отсортированный по убыванию. В одном случае будет O(n^2), а в другом O(n).
Тема неуникальных значений не раскрыта. И если массив из одинаковых чисел, то должны быть все нули.
@@serged5689 это не соответствует условиям задачи. Требуется явно найти дни, когда температура ВЫШЕ. А условия не нахождения таких дней не заданы. И это был бы хороший вопрос на собеседовании.
Классы Stack и C занимают место в куче, тратится время на инициализацию (конструкторы). Накладные расходы на объекты всегда велики. В целом, решение с обычными итерационными циклами покажет лучшую производительность и экономию памяти.
От количества данных зависит. На малом объёме - да.
В подобных задачах не учитываются расходы на инициализации и прочее, тк это задача на построение алгоритма, он мог работать с парами, что было бы быстрее, но это в задаче не рассматривается
При инициализации стека фиксированного размера мы получим лишь одну единственную концанту по инициализации. В практическом же смысле куча или стек не имеют значения когда в одном цикле мы обращаемся по указателям в непрерывную область памяти, т.к. это всегда будут затраты на помещение непрерывного блока в кэш L3 и незначительные на этом фоне затраты обращения к кэшу. Более того, если размер массива значительно будет превышать размер блока для кэша L3 (например 10^6 целых) то решение O(n*n/2) с обращением к массиву в цикле будет еще и иметь огромный штраф типа 10х по сравнению со стеком за счет оптимизаций обращения к кэшу процессора, на фоне чего затраты на разовую инициализацию стека меркнут.
@@kostyajan L3 есть не везде. Нацеливаться только на L3 это ошибка.
Ахах) только утром решал задачу и тут вечером под чийочик смотрю разбор)
Решал банальным брутфорсом (двойным циклом)
n
А чем плоха рекурсия?
Если элемент справа есть и он больше текущего, то =1 и идём дальше, иначе считаем значение для правого элемента +1
Блин, зачем ты заспойлерил стек в названии( теперь непонятно, сам ли я до стека додумался или ты подсказал
Кажется, если стек пустой, то нужно добавить в массив ответов 0 для текущей температуры i
Там создаётся массив и в Яве там итак будут нули (в отличии от си или спп)
А какую самую сложную задачу Вы встречали, если не секрет. Потому что те, что есть у вас на канале, решал бы также как, Вы... Спасибо!
Hungarian algorithm - вероятно самое сложное что могут дать на очном собеседовании (если только бар-райзер не идет в a priori нерешаемые проблемы).
@@alexanderyakovenko1735 спасибо, интересно!
@@alexanderyakovenko1735 зачем бы бар-рейзеру фигнёй страдать? Ну только если вы набираете на конкретно научную должность, где требуется algorithm design... Но тогда это не тот канал.
Вы поймите, дело совсем не в сложности задачи. Из любой тривиальной задачи можно сделать задачу бесконечной сложности. Например, увеличив размер входных данных и добавив серверов (а как решить эту же задачу, если ваш входной массив 20 петабайт и у вас есть 2000 серверов?). Или расслабив входное условие (в данном случае, расстояние до БЛИЖАЙШЕГО для с более высокой температурой). И т.п. Можно поговорить о том, как внутри устроен стек, и т.п.
Вроде можно просто динамикой решить: если предыдущий день не теплее нашего, то шагнём на столько назад, какое число мы уже заполнили для предыдущего дня и проверим получившийся день. Получается то же самое, только не нужна память под стек.
Покажи мне такое решение со сложностью < O(n^2)
@@redhook777 вот, примерно в 10 раз быстрее чем реализация через стек:
static int[] temperature(int[] t) {
int[] answer = new int[t.length];
for (int i = t.length - 1, head = t.length; i >= 0; i--) {
while (head < t.length && t[head]
@@AlexeySilichenko чем это принципиально отличается от двойного цикла?
@@SwampJay Перескоками через заведомо меньшие. И стек не нужен.
Если исходный массив температур очень большой, то вариант со стеком может оказаться предпочтительнее, чем вариант с перескоками из-за кэш миссов при большом разбросе максимальных температур одновременно попадающих в стек и находящихся в сильно разных местах исходного массива. Также вариант со стеком (буферизацией) единственный при потоковом вводе и выводе значений, естественно всё равно начиная с конца.
Тут описана работа стека как будто поставить жирафа в холодильник: открыл холодильник, поставил жирафа, закрыл холодильник. Но в действительности можно очень при этом вспотеть. Разве компилятор не делает кучу подкапотной работы при манипуляции со стеклом?
На мой взгляд стек тут явно лишний.
Следующий вариант не использует стек совсем, и имеет такое же время работы.
Используем тот факт, что используя заполненную часть массива answer и исходный массив всегда можно пройти по "элементам стека"
public int[] temperatures(int[] t) {
int[] answer = new int[t.Length];
answer[t.Length - 1] = 0;
for (int i = t.Length - 2; i >= 0; i--) {
int next = i + 1;
while (t[i] >= t[next] && answer[next] > 0) {
next += answer[next];
}
answer[i] = t[i] < t[next] ? next - i : 0;
}
return answer;
}
Очень хорошее решение! Но по-моему здесь такой же по температуре день ломает логику.
@@Vitek_23 Спасибо, изменил строгое равенство на нестрогое, теперь логика не ломается.
Я не умею в эту вашу Яву, но стек городить тут не нужно. Идём слева направо, для i-го дня ищем следующий с большей температурой (k-й). Когда находим, заполняем все дни с i-го по k-1-й количеством дней до k-го (его даже считать каждый раз не надо, считаем 1 раз и потом уменьшаем на единицу), потом i=k и всё повторяем.
И это правда _хитрая_ задача? Может Яву освоить тогда, в ней вроде платят хорошо.
Дано: [8, 6, 7, 9]. В вашем случае выйдет результирующий массив [3, 2, 1, 0], тогда как правильный - [3, 1, 1, 0].
Хорош
9:30 - Pair?
а еще что будет ? а то 4 задачи и все
class C { } -- я хлопал стоя . спасибо большое тебе , и интересно и полезно , спасибо
Мне понравилась задача. Поставил на паузу после условий. Вот такой вариант пришёл в голову, реализация на Питоне (немного учил его на карантине).
a = [13, 12, 15, 11, 9, 12, 16]
for i in range(0, len(a)-1):
print(a[i])
n = 1
while a[i+n] < a[i]:
n +=1
else:
print(str(n) + " дня")
print(str(a[-1]) +" 0 дней")
Интересный код, но работает - тоже за квадрат, если я не ошибаюсь) Примерно то же, что и предлагалось в видео как первый алгоритм.
const temperatures = [ 13, 12, 15, 11, 9, 12, 16 ]
function getTemperatureDays(arr = []) {
const result = {
[arr.length - 1]: 0
}
const stack = []
for (let i = arr.length - 1; i >= 0; i--) {
while (stack.length !== 0 && stack[stack.length - 1][1]
Очень странное решение, вместо того чтобы записывать в стек все левые числа и каждое новое сверять с поледним в стеке и как только найдем большее собирать инфу и очищать стек, вы решили пройти с конца и чекать постоянно весь стек...
И вышло что Вы к первому решению прикрутили еще и стэк
Можно хранить в стеке комплексные числа, в которых есть 2 инта. Не по назначению, но без велосипедов
мне в голову пришло решение с рекурсией. если следующий элемент больше текущего, то ответ 1. иначе берем значение рекурсивной функции следующего элемента и если оно больше нуля, то прибавляем к нему 1 и это будет наше значение. а если значение функции следующего элемента 0, то и наше значение 0.
@via6274 Хорошая идея, сначала даже поверил в неё, но ломается например на последовательности 3 1 2
@@Docik86 да. я это понял тоже почти сразу. не стал удалять коммент 🙂
Спасибо за решение. Только вот во внешнем цикле из t.Length следует вычесть единицу, иначе будет выдана ошибка о выходе за пределы массива. Удачи.
Можно и слева-направо ответы получать тем же способом
амортизированная линия, а не обычная получается
Обычная линия, при чем тут амортизированная?
ну это простенький алгоритм, на этих собесах алгоритмы по сложнее задают, а потом забивают вопросами про линух
А нельзя засунуть весь массив в массив индекс, значение. После отсортировать его по возрастанию значения. а потом просто пройтись и вычитанием последующего индекса из предыдущего получить ответ?
Нельзя, могут получиться отрицательные значения. Даже если было бы можно, сложность сортировки - O(N*logN).
Совсем небольшое дополнение, нам по идее понадобится условие для самой первой итерации, чтобы сохранить 0
0-ой элемент в любом случае будет сохранён, зачем условие?
Лучше рекурсия + динамическое с Хеш-мапой, как по мне. answer[i] = answer[i-1]+1 || 1 || 0
на рекурсию может просто памяти не хватить при больших массивах данных
@@user-gk2kn3ri7z Рекурсия внутри єто тот же стек. Главное запоминать результат в hashMap для посчитаньіх уже ответов.
Разве время работы второго алгоритма (стек) не O(n) в худшем случае.
Например:
15 10 11 12 13 14 16
Ну ясен пень, время работы не может быть меньше размера ответа