Подготовка к собеседованию в Google - Хитрая задача на Стек

Разбираем довольно сложную алгоритмическую задачу по программированию с применением стека. Ее могут спросить на собеседовании в Google, Amazon и Facebook.
Эта задача на LeetCode: leetcode.com/p...

[@sashalukin]

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

[@old_relokant]

Вы прекрасно объясняете алгоритмы и структуры данных. Это очень большая редкость. Надеюсь что Вы вернётесь к ведению канала и будете продолжать просвещать начинающих it-специалистов.

[@KirillFrolov77]

Это не только для начинающих. :-))

[@bohdansolonenko6554]

Если не ошибаюсь, то стек тут не нужен, проблему можно решить за это же время без дополнительной памяти: 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; }

[@gamadrillo]

Не ошибаешься, скрипач не нужен.

[@gandibaat3637]

Что-то подсказывает, что ты прав, и сложность в твоем случае линейная, несмотря на то, что здесь цикл в цикле, и while иногда выполняется несколько раз. Можешь сказать, так ли это?

[@gandibaat3637]

@@bohdansolonenko6554 да, теперь понял. Действительно, количество прыжков не больше, чем количество stack.pop() из реализации в видео и сложность не возрастает. Красиво, спасибо

[@kostya_superovotes8610]

Да, круто)

[@pagrus7]

Линейное время неочевидно. В варианте со стеком линейное время доказывается доказывается через работу со стеком: - В итерации цикла добавляется 1 элемент, и рассматривается [1 + количество удаляемых элементов]. - За время работы всего алгоритма каждый элемент удаляется один раз. - Итого линейное количество итераций и линейное количество операций со стеком за весь алгоритм Здесь тоже нужно как-то доказывать что res[i] рассматривается константное количество раз.

[@iliarodin6557]

Александр, очень нравится как вы объясняет материал. Спокойно и понятно. Спасибо.

[@kushok93]

Можно идти по списку и в прямом порядке: 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

[@tormizor]

Парень прирожденный препод! :) Очень доходчиво.

[@PointWand]

Прекрасное лаконичное изложение материала, спасибо. В стек не обязательно сохранять значения, достаточно просто индексы. По ним в исходном массиве находим значение.

[@KirillFrolov77]

Кстати, да. LinkedList - тоже вариант

[@FrontNinja]

хорошее дополнение 👍👍

[@MaratAshrafzianov]

Читать список не последовательно довольно тяжело для процессора (почитайте про кеширование). Так что лучше все же сохранять значения также.

[@PointWand]

@@MaratAshrafzianov 1.Если все данные записаны в кеш процессора, то разницы никакой. 2. Размер данных меньше минимум в 2 раза. Неизвестно, что станет бутылочным горлышком в дальнейшем и какие данные поместятся в кеш полностью. 3. При текущем алгоритме данные тоже пишутся не последовательно (попеременное обращение в разные области). 4. Экономия на спичках, коим является учитывание кэш процессора, является самым затруднительным и с минимальным приростом по производительности действием. Тем более, когда пример дан на Java

[@jury2753]

Лучшее объяснение алгоритмов, нет слов, просто потрясающще!!!

[@powerhead]

Хорошее решение. Нет необходимости хранить в стеке значения температур, достаточно класть туда только индексы: 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]

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

[@Svetoz]

Интересная опция! На сложность (О) не влияет, но может быть принципиальным если значение не просто цифра, а сложный тяжелый объект.

[@powerhead]

@@by0uki это алгоритмическая задача, здесь не идет речь о работе с базой, данные находятся в памяти. Если хранить в стеке только индесы, то памяти потребуется в два раза меньше, а скорость не изменится

[@Alkor2399]

С таким кайфом вообще смотрю, спасибо огромное

[@azatakhunov6061]

Решение со Stack прошло проверку. Спасибо за видео! лайк и подписка

[@Vitek_23]

Спасибо за пример и хорошее объяснение! 👍

[@HideDJeker]

С временной сложностью не совсем очевидно, но именно взаимодействий со стеком (вставок и удалений) в худшем случае

[@dmitry7464]

Спасибо

[@KirillFrolov77]

Тут на помощь придет ещё одно наблюдение: на каждом шаге мы вставляем ровно один элемент и удаляем ноль или более. Поскольку мы всего вставляем максимум n элементов, то и удаляем мы всего максимум n элементов. Операции со стеком занимают время O(1), так что тут все достаточно просто: общая амортизарованная сложность по времени O(n). И по памяти тоже O(n).

[@MagicMightNew]

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), до того как посмотрел разбор. Спасибо большое за задачу :)

[@mtdatton1157]

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

[@denicfor3811]

Отличное объяснение! У меня сначала появилась идея просто отсортировать массив по убыванию с сохранением индексов и потом бежать по нему и выделять в подмассив длинны n ответы по индексу элемента в подмассиве, но ваш вариант определенно лучше во всех случаях)

[@plumbumer8424]

Спасибо, хорошее решение. Сам решал так же со стеком, однако массив проходил в прямом порядке. Как по мне так короче и проще для понимания, при аналогичной сложности по времени и памяти: 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=" ")

[@rtm0076]

Я Андрей и я работаю кассиром в Пятерочке. Надо начинать не с последнего элемента а предпоследнего так как у последнего всегда будет 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; } }

[@bykaxagod597]

Не смотрите это видео зимой! По ролика мозг перед числами рисовал мне минус. Поэтому у меня возникал постоянный вопрос: "Какого хрена 15, теплее чем 9. - 9 это же теплая зимняя погода, а - 15 это ближе к дубаку)))

[@Svetoz]

Интересная задача и очень понятное объяснение решения! Спасибо!

[@dmytro3730]

Отличное видео, жаль что нет новых.

[@gv0zdik]

Очень крутая подача, автору респект!

[@АлексейТарасов-х9е]

Какой же ты крутой бро, лайк тебе)))

[@Selex95]

Красава вапще, я не могу просто над тобой, лайк, подписка, и high recommended

[@kostya_superovotes8610]

Я смотрю, многие пишут, что сложность не поменялась и всё ещё 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 операции. Вообще, операций может быть немного больше, ведь мы можем какие переменные ещё подключать и тд, но суть в том, что из конечное, небольшое и с фиксированным максимумом количество.

[@eugeneshcherbo9821]

Мне еще помогает понять сложность тот факт, что ни один элемент массива не попадет в стек более одного раза, а значит внутренний цикл while В СУММЕ будет выполняться O(n) раз.

[@lawamoril]

У тебя ещё есть прогонка в стеке. А стек у тебя может по размеру быть как массив. И что бы найти в стеке нужный ты по факту получаешь O(n*n). Сложность же считается для алгоритма, а не для определённого решения. По этому O(n*n/2) тут

[@airn587]

@@lawamoril прогонки не будет каждый раз, а максимум один раз, после чего элементы удалятся. Поэтому О(n). Чтобы другим способом понять можно на примере рассмотреть крайние примеры "6 1 2 3 4 5" и "5 4 3 2 1 6" и увидеть, как красиво работает в обоих случаях стек. В то время как в 2 примере решение без стека, с циклом, будет выполняться за O(n^2) ((если про количество итераций, то (n*n/2), но 1/2 в O нотации опускаем).

[@KirillFrolov77]

​@@lawamoril амортизированно по всем шагам мы удаляем из стека максимум n элементов, добавляем всегда n элементов. Не будет квадратичной сложности.

[@egorrichmining1069]

@@KirillFrolov77 Амортизированно == суммарно?

[@ДмитрийКнягинин]

Очень хорошее объяснение и залача, спасибо

[@withotsoul7252]

Спасибо большое бро! Канал топовый!

[@efim.22]

Можно сделать еще проще: Не сохранять индексы. А кол-во суток через которое будет более теплый день будет показывать количество удалений элементов из стека + 1

[@kushok93]

На первый взгляд ваше утверждение кажется логичным, но на видео контрпример для самого левого элемента = 13. Кол-во удалений из стека на этом этапе явно больше двух

[@AlexMitinPlus]

Я бы загнал в бинарное дерево с сохранением индекса. Тогда для ответа нужно просто пройти по дереву в глубину в режиме inOrder. И для каждого значения посчитать разницу с предыдущим индексом.

[@mrlaster325]

Тогда будет O(nlogn) + бинар дерево писать

[@KirillFrolov77]

Само создание дерева уже O(n*log(n)). И это мы ещё решать не начали. :-))

[@MrPhantomdc]

Если в стеке нет элементов, в массив ответов нужно записать 0, а то в твоем тесткейсе, как я понимаю, последний день, ровно как и день с максимальной температурой, не обрабатывается никак.

[@RSkvor]

Однако это не так уж и сложно обрабатывается, здесь важнее алгоритмика нежели полнота

[@levekasov3795]

массив ответов - это массив маленьких интов, что значит по умолчанию они все 0 и нет необходимости этот 0 еще раз проставлять.

[@gandibaat3637]

Массив примитивов (например, int[]) в Java инициализируется значениями 0. Поэтому массив уже заполнен элементами, равными 0.

[@projeqt9243]

@@gandibaat3637 а при чем тут джава? это алгоритмическая задача

[@gandibaat3637]

@@projeqt9243 претензии-то к конкретной реализации. А пример в видео написан на Java. Я и объясняю, почему принудительно писать в массив ответов нули не нужно.

[@ValKozh22]

Спасибо за видео, понятно объясняете

[@Poli.Pavlovich]

Благодарю за видео!

[@AlexeySilichenko]

вот более эффективный алгоритм (быстрее примерно в 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]

[@ihormay3418]

Стек не дает преимуществ. Кажется вроде он по памяти оптимизирован, но можно исполбзовать массив ответов и массив индексов следующего теплого дня. Да, массив индексов будет как массив ответов по длине, но у тебя нет лишней коллекции чтобы хранить температуры дней. Хотя ладно, пока писал понял, что если исходный массив огромный, а мы ожидаем, что стек по ходу программы будет маленький, то выигрышь есть. А мои предыдущие размышления имеют вес только для вырожденного случая. Ты прав

[@MrHArdenX]

Можно не создавать ещё коллекцию по хранению температур, можно обойтись самой высокой, чтобы потом перепрыгивать по элементам. Не особо хотел подробно описывать, может некоторым захочется самому подумать.

[@sergeynazarov2473]

Это не просто стек, это возрастающий монотонный стек (increasing monotonic stack), в котором значения только увеличиваются. И зачем отдельный класс для хранения так же не понятно, можно хранить элементы стека в формате массива [value, index].

[@toster8240]

Позитивная подача и интересный материал !

[@Kalin_cheetah]

Ох блин, я несколько дней думал над задачей, решение сам придумал, но двигался слева направо и код получился куда менее лаконичным (на С++). На leetcode по сложности тоже прошел тесты.

[@Alessandro133]

Еще не просмотрел видео, только прослушал условие и начал думать, а тут на глаза попалось название... Зачем же так сразу все палить :)

[@KirillFrolov77]

Мое персональное мнение, что ожидать решение такого типа - это против правил. Если для формулирования оптимального алгоритма надо знать приемчики - то такое интервью не дает вам никакой полезной информации. Ну или вернее, если человек знает это решение - то это подтверждение того факта, что он готовился, а не того, что он чего-то там умеет сам. В Amazon'е это бы классифицировали как trick question и в обсуждении не зачли бы. А интервьюеру сказали бы, чтобы он больше этот вопрос не использовал. Что касается самого подхода, не сказаны главные слова. Надо сказать, что, мол, обратим внимание, что в любой момент времени нас интересуют ИСКЛЮЧИТЕЛЬНО дни справа, в которые температура была ВЫШЕ температуры текущего рассматриваемого дня. Поэтому все температуры, которые мы уже встретили справа и они ниже, можно смело выкидывать из рассмотрения, в любом случае расстояние от любой более низкой температуры слева до текущей будет короче, чем до любой более низкой температуры справа. Вот именно из этого наблюдения следует оптимальное решение, а вовсе не из переборного решения. Использвать стек или нет - решение наживное, linked list тоже пойдет, там все операции с головой списка тоже O(1), как рту стека

[@Arsen0895]

9:29 как нет?? почему бы не использовать мапы???

[@levorlov8788]

Интересная задача. Спасибо вам за такое хорошее и понятное объяснение!)

[@MaHsepp]

не правильно использовать "свойства" length, во втором параметре цикла for (let a = 0; a < t.length; a++) потому что в таком случае каждый следующий шаг цикла будет каждый раз тратить время на определение t.length. более быстрее будет сразу задать в первом параметре for (let a = 0, b = t.length; a < b; a++)

[@cringoulique]

неправильно писать тяжелочитаемый код, выигрыш в производительности проигрыш в производительности очень незначителен, но код становится заметно легче для восприятия

[@MaHsepp]

@@cringoulique Вообще-то во многих крупных корпорациях выигрыш в производительности как раз таки очень значителен и является самым важным фактором, даже если код становится тяжелочитаемый. Потому что пользователи куда важнее чем программисты читающие код. Именно поэтому выигрыш в производительности очень даже значителен не смотря на тяжелочитаемый код. Особенно когда речь идёт о гиганстких обработок данных. Да и к тому же, с какой стати код становится тяжелочитаемый ?? Изначально я привёл шапку цикла из примера видео, в нём 34 символа. Дополнение кода изменяет длину шапки всего до 37 символов. С какой стати такая разница превращает код в тяжелочитаемый, если само содержимое цикла не меняется.

[@АлександрШ-й5ж]

Классное объяснение!

[@alexyevdokimov642]

А вы в тактах процессора считали, что дороже циклы в кэше проца x86_64 крутить или стек городить с new + delete. Вот это как раз и есть разница в ява программистах и тех, кто на ассемблере работать умеет.

[@serged5689]

Разница инженера и кодера в том что инженер понимает что происходит при n -> стемящихся к большим числам.

[@alexyevdokimov642]

@@serged5689 "Я это сделал не в интересах истины, а в интересах правды" (с) Вы чего этим сказать то хоть хотели по разбору конкретно этого прикладного кейса?

[@xz8928]

@@alexyevdokimov642 в алгоритмических задачах предполагается что решение будет быстрым при больших n

[@Qwerty-fn3rf]

Спасибо 🔥

[@Георгий-ь6с]

Для меня было проще обратное решение: проходить массив слева направо, добавлять в стэк кортеж: (температура + индекс) , и до этого вынимать из стека все показатели с температурой меньше, чем текущая и записывать в результат разность их индексов.

[@sergeychigarev255]

Сильно зависит от условий, конечно. Почему-то снова оценка О() построена на том, что работа со стеком - бесплатная. Причем как удаление / добавление элементов, так и поиск нужного числа в стеке - внезапно бесплатный?! как это так? Это же совершенно не соответствует действительности! Оценка О(n) явно неправильная. В зависимости от везения (т.е. от исходных данных) вычислительная сложность решения со стеком будет на промежутке O(n)....O (n2). И это если не учитывать добавление / удаление в стеке, которое, повторюсь, совершенно не бесплатное. Однако если последовательность дней ну оочень длинная и температура ходит "туда-сюда" - то выигрыш в решении со стеком будет, это да.

[@mixapro1971]

Я что-то не понял условие задачи - ведь для каждого дня в данном примере самая высокая температура будет последняя, почему для пнонедельника будет другой день? Перечитал условие в другом месте, более понятно. Нужно найти день после выбранного дня, температура которого превышает температуру выбранного дня.

[@IT-sn3vk]

Видео про Google интервью - kzbin.info/www/bejne/Z3apqH-hl86HpMk Жду Ваших комментариев. Like и Subscribe приветствуются!

[@hmixa]

Все замечательно, только маленький диссонанс: с одной стороны собеседование в Гугл, а с другой стороны объясняем что такое стек.

[@ДаниилМонахов-р8ч]

Большая дорога начинается с первого шага. :)

[@Romas333333]

Не совсем понял второй ответ, возможно потому что далек от програмирования. Разве для 4 элемента массива (9) следующим большим не будет 5элемент (12) ? Просто исходя из полученной информации в стеке на 4 элемент соответственно выдаст нижний элемент (16)? И если первый элемент массива будет наибольшим, что мы получим на выходе? Не заметил проверку на это.

[@kostya_superovotes8610]

Да, правильно, для 4-ого элемента ответом будет 5-ый элемент и алгоритм из ролика так и считает. Когда мы доходим до этого самого 4-ого элемента мы уже прошли 5-ый и 6-ой, поэтому наш стек будет выглядеть так: 12(5), 16(6). А начинаем мы проходить по нему с вершины, то есть с 12, и поскольку сразу натыкаемся на число больше 9-ти, берём его ответом. Таким образом для 4-ого элемента ответом будет 5-ый.

[@Romas333333]

@@kostya_superovotes8610 Спасибо! Теперь понял. Думал сперва полностью формируется стек для всего массива, а потом осуществляется перебор.

[@Alex-q9o5k]

блин, я тоже сразу решил идти с конца. но так как вообще не работал со стеком. не подумал про него. а подумал про обычный массив🤔

[@edward.vstock]

вот блин, в названии видео был ответ, а я уже думал о сортировке с сохранением индексов и прочие усложнения

[@Camelot1399]

Понятно и без воды, лайк 👍

[@georgyg1531]

Чем второй способ с созданием, добавлением и удалением объекта в стекле лучше первого? Не разобрали такты процессора и работу с кэшем.

[@All-jl8yi]

Так и не понял зачем стек когда можно хранить 1 число (последнее добавленное в стек), а его ответ укажет где находиться следующее «в стеке»

[@serafim4372]

Потому что возможна ситуация при которой данные только последнего значения не будут достаточными для правильного ответа. Например, если у нас в стеке числа (9, 12, 16) , то для случаев нового дня с температурой 11 и 14 будут разные ответы, которые не получить только из последнего ответа для 9, нужен именно стек всех предыдущих значений.

[@some_light]

@@serafim4372 да, но в примере у 9 тоже посчитано расстояние, на которое сразу можно перейти дальше и тд. Т е работать будет как в стеке, но без доп структуры, тк можно считать, что каждый элемент имеет ссылку на следующий в "стеке". и нам достаточно помнить индекс "верхушки"

[@Hamsters_Rage]

и в каком месте второго решения мы в ответы 0 кладем для 16?

[@Dudarik]

А это уже тест на внимательность :) Вы приняты в Гугол :D

[@kirilllyam2744]

Массив изначально 0 заполнен в джаве

[@vitalyproxtor3229]

чувствую как становлюсь умнее...🤗

[@cheefoxcheefox2372]

Вроде можно просто динамикой решить: если предыдущий день не теплее нашего, то шагнём на столько назад, какое число мы уже заполнили для предыдущего дня и проверим получившийся день. Получается то же самое, только не нужна память под стек.

[@redhook777]

Покажи мне такое решение со сложностью < O(n^2)

[@AlexeySilichenko]

@@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]

[@SwampJay]

@@AlexeySilichenko чем это принципиально отличается от двойного цикла?

[@eyezaryvideos]

@@SwampJay Перескоками через заведомо меньшие. И стек не нужен.

[@eyezaryvideos]

Если исходный массив температур очень большой, то вариант со стеком может оказаться предпочтительнее, чем вариант с перескоками из-за кэш миссов при большом разбросе максимальных температур одновременно попадающих в стек и находящихся в сильно разных местах исходного массива. Также вариант со стеком (буферизацией) единственный при потоковом вводе и выводе значений, естественно всё равно начиная с конца.

[@lermos]

Спасибо. Всё шикарно

[@oops61rus]

А что произойдет в случае, если у нас день среди недели был самым жарким? Как будто бы этот нюанс не обработан в решении. Не знаю, как в джаве это будет выглядеть. Джаваскрипт бы выбросил ошибку Но за объяснение спасибо большое

[@almirdavletov535]

Крутое решение! 💪

[@dok3522]

На мой взгляд стек тут явно лишний. Следующий вариант не использует стек совсем, и имеет такое же время работы. Используем тот факт, что используя заполненную часть массива 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]

Очень хорошее решение! Но по-моему здесь такой же по температуре день ломает логику.

[@dok3522]

@@Vitek_23 Спасибо, изменил строгое равенство на нестрогое, теперь логика не ломается.

[@Avorthoren]

Интересно, почему вместо прямолинейного решения с проходом слева направо выбрано по сути эквивалентное с проходом справа налево :)

[@gandibaat3637]

Если ты идешь слева направо и хочешь решить задачу за один проход - ты ничего не знаешь о будущих температурах, соответственно ничего не знаешь о расстоянии до ближайшего дня, когда будет теплее. Если бы условие стояло "найти количество дней до дня в прошлом, когда было теплее", тогда бы можно было пройти слева направо и нельзя - справа налево.

[@Avorthoren]

@@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

[@gandibaat3637]

@@Avorthoren справедливо и вроде работает на первый взгляд. Справа налево логичнее и проще для понимания как-то, на мой взгляд - считаем ответ для дня в массиве в тот момент, когда проходим по нему

[@Avorthoren]

@@gandibaat3637 Ну такое :) Вроде не менее логично пройти элемент, и, когда дойдём до элемента с большей температурой, вычислить ответ для исходного :)

[@lurgee1706]

@@gandibaat3637 Справа налево можно вообще без стека решить, просто использовать инфу о уже пройденных днях.

[@eugenicko]

А чем хуже, если вместо отдельного класса в стек класть массивы из двух значений?

[@Дмитро-к1р]

Кажется, если стек пустой, то нужно добавить в массив ответов 0 для текущей температуры i

[@HolyDel]

Там создаётся массив и в Яве там итак будут нули (в отличии от си или спп)

[@vadimorlov4986]

"Поскольку каждый день мы можем добавить и удалить лишь 1 раз, то сложность O(n)." Когда мы доходим до дня 2 с темп 15, то мы добавляем 1 раз, но удаляем 2 раза (удаляем день 3 и день 5). Или я что-то путаю? Кто-то может объяснить, пожалуйста, почему сложность O(n), даже в случае, когда мы имеем 100000 элементов и доходим до 0-ого элемента, который имеет, допустим, самую высокую температуру и в худшем случае мы вынуждены проходится обратно по всему стеку и удалять все дни по очереди до 100000-ого элемента?

[@chichkan87]

Имеется в виду, что каждое число из массива может в худшем случае один раз попасть в стек и один раз из него удалиться. Получается максимум 2*N операций. Если мы в конце удалили 100000 элементов, это значит, что мы до этого ни разу ничего не удалили и 100000 раз добавили. Получается, мы сделали для 99999 чисел по одному добавлению и для одного последнего числа 100000 удалений. Всего как раз 2*N.

[@vadimorlov4986]

@@chichkan87 спасибо большое 🙏🏼 Собрался читать «Грокаем алгоритмы». Про О большое теперь что-то знаю :)

[@andreychameleon2135]

Тут описана работа стека как будто поставить жирафа в холодильник: открыл холодильник, поставил жирафа, закрыл холодильник. Но в действительности можно очень при этом вспотеть. Разве компилятор не делает кучу подкапотной работы при манипуляции со стеклом?

[@_V_I_A_]

мне в голову пришло решение с рекурсией. если следующий элемент больше текущего, то ответ 1. иначе берем значение рекурсивной функции следующего элемента и если оно больше нуля, то прибавляем к нему 1 и это будет наше значение. а если значение функции следующего элемента 0, то и наше значение 0.

[@Docik86]

@via6274 Хорошая идея, сначала даже поверил в неё, но ломается например на последовательности 3 1 2

[@_V_I_A_]

@@Docik86 да. я это понял тоже почти сразу. не стал удалять коммент 🙂

[@vladimirterentev3085]

Круть, спасибо)

[@Д-рВедьмак]

Изящно! :)

[@ilias3624]

Объясните плиз, почему в первом случае сложность считается как О(n^2). больше похоже на О(n^2 / 2). Из примера в видео с n = 7 получаем, что мы в худшем случае пройдем по массиву 6+5+4+3+2+1 = 21 раз, или тут деление на 2 это как константа и потому отбрасывается?

[@МаксимЯковлев-п8ш]

Константы выностяся за нотацию, да

[@elmaminsk5411]

Можно и слева-направо ответы получать тем же способом

[@slavaguk3128]

Можно хранить в стеке комплексные числа, в которых есть 2 инта. Не по назначению, но без велосипедов

[@indirayessimova651]

ну это простенький алгоритм, на этих собесах алгоритмы по сложнее задают, а потом забивают вопросами про линух

[@v.n7k]

Лучше рекурсия + динамическое с Хеш-мапой, как по мне. answer[i] = answer[i-1]+1 || 1 || 0

[@ИльяСултанов-у6з]

на рекурсию может просто памяти не хватить при больших массивах данных

[@v.n7k]

@@ИльяСултанов-у6з Рекурсия внутри єто тот же стек. Главное запоминать результат в hashMap для посчитаньіх уже ответов.

[@developer6508]

9:30 - Pair?

[@НадеждаТарасова-ю1е]

Не нужны ни стеки, ни вложенные циклы. Представьте себе график функции температуры. Он имеет локальные максимумы и минимумы. Информацию о них можно собрать за один проход по массиву. Затем формируем массив результатов в найденных точках локальных максимумов ставятся разницы соответствующих значений, а между ними последовательности из единиц для возрастающих участков и куски геометрических прогрессий для убывающих. Стек действительно разумно использовать - в него имеет смысл вносить позиции локальных экстремумов.

[@vhack3712]

Ничосе какая умная, а алгоритм можно увидеть?

[@i.am.rossalex]

А какую самую сложную задачу Вы встречали, если не секрет. Потому что те, что есть у вас на канале, решал бы также как, Вы... Спасибо!

[@alexanderyakovenko1735]

Hungarian algorithm - вероятно самое сложное что могут дать на очном собеседовании (если только бар-райзер не идет в a priori нерешаемые проблемы).

[@i.am.rossalex]

@@alexanderyakovenko1735 спасибо, интересно!

[@KirillFrolov77]

​​@@alexanderyakovenko1735 зачем бы бар-рейзеру фигнёй страдать? Ну только если вы набираете на конкретно научную должность, где требуется algorithm design... Но тогда это не тот канал. Вы поймите, дело совсем не в сложности задачи. Из любой тривиальной задачи можно сделать задачу бесконечной сложности. Например, увеличив размер входных данных и добавив серверов (а как решить эту же задачу, если ваш входной массив 20 петабайт и у вас есть 2000 серверов?). Или расслабив входное условие (в данном случае, расстояние до БЛИЖАЙШЕГО для с более высокой температурой). И т.п. Можно поговорить о том, как внутри устроен стек, и т.п.

[@ВасилийКоровин-г9э]

Я не умею в эту вашу Яву, но стек городить тут не нужно. Идём слева направо, для i-го дня ищем следующий с большей температурой (k-й). Когда находим, заполняем все дни с i-го по k-1-й количеством дней до k-го (его даже считать каждый раз не надо, считаем 1 раз и потом уменьшаем на единицу), потом i=k и всё повторяем. И это правда _хитрая_ задача? Может Яву освоить тогда, в ней вроде платят хорошо.

[@Army_of_Earth]

Дано: [8, 6, 7, 9]. В вашем случае выйдет результирующий массив [3, 2, 1, 0], тогда как правильный - [3, 1, 1, 0].

[@danyday8098]

Здорово, но зачем стек, если в массиве answer уже хранятся отностительные данные об индексах отработанных элементов? Вроде можно вообще без стека

[@ВладиславИерусалимов]

+

[@edwardkrasovsky2520]

Классы Stack и C занимают место в куче, тратится время на инициализацию (конструкторы). Накладные расходы на объекты всегда велики. В целом, решение с обычными итерационными циклами покажет лучшую производительность и экономию памяти.

[@artemkonoplin2143]

От количества данных зависит. На малом объёме - да.

[@力工升乃口乚工片]

В подобных задачах не учитываются расходы на инициализации и прочее, тк это задача на построение алгоритма, он мог работать с парами, что было бы быстрее, но это в задаче не рассматривается

[@kostyajan]

При инициализации стека фиксированного размера мы получим лишь одну единственную концанту по инициализации. В практическом же смысле куча или стек не имеют значения когда в одном цикле мы обращаемся по указателям в непрерывную область памяти, т.к. это всегда будут затраты на помещение непрерывного блока в кэш L3 и незначительные на этом фоне затраты обращения к кэшу. Более того, если размер массива значительно будет превышать размер блока для кэша L3 (например 10^6 целых) то решение O(n*n/2) с обращением к массиву в цикле будет еще и иметь огромный штраф типа 10х по сравнению со стеком за счет оптимизаций обращения к кэшу процессора, на фоне чего затраты на разовую инициализацию стека меркнут.

[@saymannskable]

@@kostyajan L3 есть не везде. Нацеливаться только на L3 это ошибка.

[@alekseypavlov2539]

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]

[@ВячеславКабулахин]

А чем плоха рекурсия? Если элемент справа есть и он больше текущего, то =1 и идём дальше, иначе считаем значение для правого элемента +1

[@andreiegorov556]

Если несложно, объясните пжста по первой части: при решении с двумя циклами получается, что в решение попадают значения из массива большие по условию, но перебор каждый раз начинается с начала массива, ответы попадают неверные

[@Козя3]

Перебор начинается не с начала массива, а с элемента на котором мы находимся +1 Ответы попадают верные, однако мы лишний раз проходимся по элементам которые не могут нам подойти Во втором случае мы эти элементы убираем

[@andreiegorov556]

@@Козя3 спасибо)

[@andreiegorov556]

@@Козя3 всеравно не получается( я решаю в питоне, запускаю два цикла первый с перебором по значениям, второй с перебором по индексам. Индексы являются решением, но невсегда верны( т.к. каждый раз перебор начинается с начала списка. Помогетп пжста, уже две недели пытаюсь решить, и бросить не могу((

[@ramzess1426]

Но ведь можно использовать рекусию, или я заблуждаюсь? Просто тогда получается что Оn = (n-1)*n/2. Но я в это мне уверен...

[@kostya_superovotes8610]

Сложность будет 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 операции. Вообще, операций может быть немного больше, ведь мы можем какие переменные ещё подключать и тд, но суть в том, что из конечное, небольшое и с фиксированным максимумом количество.

[@powerhead]

На практике, решение с рекурсией работает быстрее 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; } }

[@someone1111212312312]

@@powerhead Сорри за вопрос старому сообщению, но рекурсия - это же тот же стек, только в него ложат не наши данные а текущее состояние системы. Как оно может быть быстрее? Кто знает?

[@timbyxty]

амортизированная линия, а не обычная получается

[@isting4741]

Обычная линия, при чем тут амортизированная?

[@DIMADima-np1jg]

а еще что будет ? а то 4 задачи и все

[@michael200kg]

А нельзя засунуть весь массив в массив индекс, значение. После отсортировать его по возрастанию значения. а потом просто пройтись и вычитанием последующего индекса из предыдущего получить ответ?

[@ИльяАгафонов-х4у]

Нельзя, могут получиться отрицательные значения. Даже если было бы можно, сложность сортировки - O(N*logN).

[@michaelshkolnik9172]

Спасибо за решение. Только вот во внешнем цикле из t.Length следует вычесть единицу, иначе будет выдана ошибка о выходе за пределы массива. Удачи.

[@ЭмиаКирицугу]

Где ты тут время O(N) увидел? Это такой же вложенный цикл, на сравнение и итерацию по стеку компьютеру внезапно тоже надо время тратить. И для каждого элемента может быть до N переходов по стеку, так что в худшем случаи будет O(N^2)

[@Vitek_23]

"каждый день мы можем добавить и удалить из стека только один раз", поэтому это скорее O(2n) -> O(n), если я правильно понимаю.

[@ЭмиаКирицугу]

@@Vitek_23 В худшем случае для каждого элемента придется проверить весь стек, в котором в худшем случае будут почти все элементы.

[@vitlito]

Спасибо!

[@AndreyTorlopov]

Почему так мало видосов? Мне кажется, надо заняться каналом и запилить новые алгоритмы.

[@Leonard_Gray]

Приходишь на собеседование. Решаешь простую задачку, и тут ХЕРАК! Как ты уже должен служить, пока тебе не исполнится 510 лет! Потому что именно столько лет вам потребуется, чтобы оплатить полный боевой комплект силовой брони МК-2, которую вы потеряли! Поняли, рядовой?! Свободны!

[@АльбертИслибаев]

Блин, зачем ты заспойлерил стек в названии( теперь непонятно, сам ли я до стека додумался или ты подсказал

[@mr.farfai]

Разве время работы второго алгоритма (стек) не O(n) в худшем случае. Например: 15 10 11 12 13 14 16

[@АдамСмит-ы7р]

Ну ясен пень, время работы не может быть меньше размера ответа

[@keksinjo]

Совсем небольшое дополнение, нам по идее понадобится условие для самой первой итерации, чтобы сохранить 0

[@yarovoyyyyyyy]

0-ой элемент в любом случае будет сохранён, зачем условие?

[@vitaliyvasilenko1291]

На уникальных значениях температур оба алгоритма отрабатывают одинаково. Но пропустите через них массивы с неуникальными значениями - результаты кого-то могут удивить. А так тема интересная, объяснено замечательно. Спасибо Саша!

[@KirillFrolov77]

Ничего подобного, совершенно не одинаково. Возьмите массив уникальных температур отсортированный по убыванию. В одном случае будет O(n^2), а в другом O(n).

[@serged5689]

Тема неуникальных значений не раскрыта. И если массив из одинаковых чисел, то должны быть все нули.

[@KirillFrolov77]

@@serged5689 это не соответствует условиям задачи. Требуется явно найти дни, когда температура ВЫШЕ. А условия не нахождения таких дней не заданы. И это был бы хороший вопрос на собеседовании.

[@Anopeng]

Я не пойму, почему скорость первого алгоритма - O(n^2). Можно убедиться в этом: function test_O(n) { o = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { o++; } } return o; } test_O(7) // 21, но вот O(7^2) = 49

[@ДенисТимків-ь5ц]

починаю вивчати джаву, але як математик - максимальна кількість операцій у вказаному у відео і у вашому коментарі циклі рівна (n^2 - n)/2, вивчив це ще в 10 років, коли з хлопцями грали драбинки на турніках:)

[@ДенисТимків-ь5ц]

ну як не крути - всеодно це квадратична залежність.

[@alexuspro26]

Рассуждения хороши, но умозаключение надо доделать. 3 - 3 7 - 21 10 - 45 20 - 190 50 - 1225 150 - 11175 Теперь если построить график, характер зависимости будет вполне очевидно отличаться от линейного в пользу квадратичного.

[@chanel77788]

Ох и багов будет в такой проге