Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 25
Задачи забавные, хотя кажется что на собеседовании такое встретить можно только в какой-то фантасмагорической конторе. Да, припоминаю, в Biocad мне показывали задачку которая хитроумным образом сводится к перемножению с помощью БПФ или что-то в этом духе - но представляется что процент задач и соискателей такого класса очень невелик :)
В любом случае спасибо за статью. Наверное аккуратнее было бы назвать эту штуку "принципом" или "идеей" нежели "структурой данных" (т.к. данные она эффективно профукивает по большей части, она не для хранения строго говоря) - но в качестве "очертить общий подход" - это очень хорошо!
Ну и конечно использование реального стека в вашем коде не выглядит супер-эффективным - вместо этого поштучного "попанья" надо использовать обычный массив с указателем на "верхушку" и двоичным поиском находить куда вставляется очередной элемент и "переключается" указатель.
в Biocad мне показывали задачку которая хитроумным образом сводится к перемножению с помощью БПФ
Между БПФ и монотонным стеком - пропасть по сложности (если БПФ надо было запилить вручную). Ваш кейс действительно очень редкий, а вот поймать сабж на алгосекции вполне реально.
Спасибо за комментарий! По поводу собеседований, изначально думал включить в обзор задачу лёгкого уровня, которая могла бы с большей вероятностью встретиться. Но в конце концов решил что задача про температуры лучше проиллюстрирует идею и не стал загромождать статью.
Насчёт эффективности, согласен. Цель была скорее максимальная лаконичность и наглядность кода.
Ну и конечно использование реального стека в вашем коде не выглядит супер-эффективным - вместо этого поштучного "попанья" надо использовать обычный массив с указателем на "верхушку" и двоичным поиском находить куда вставляется очередной элемент и "переключается" указатель.
Навскидку (могу ошибаться) это не позволит существенно уменьшить количество сравнений. Стек будет большим после долгих монотонных отрезков массива, на таких отрезках у нас одно сравнение на итерацию. Выигрыш достигается, когда монотонность меняется в обратную сторону, причем каждая итерация скидывает со стека сразу много значений. Но таких итераций будет сравнительно мало. А если скидывается понемногу, то там нет особого бонуса от двоичного поиска. В общем, надо смотреть конкретные кейсы и проверять на практике.
Навскидку (могу ошибаться) это не позволит существенно уменьшить количество сравнений.
Подтверждаю. Это даст O(n log n) алгоритм вместо O(n). Это только если сравнения считать. Крайний случай, когда удалятся из стека будет только один элемент. Тогда там будет Log(n) + log(n-1) + ... = O(n log n).
Использование бинпоиска тут бесполезно.
В общем, надо смотреть конкретные кейсы и проверять на практике.
ну, резонно, от характера данных зависит
но кстати отсюда может получиться интересный кейс иллюстрирующий пример что бинарный поиск вовсе необязательно должен делить ровно пополам :)
Не важно какой там характер данных. При любом наборе данных удаление из стека по одному элементу будет O(1) амортизационно. Если мы смотрим на весь алгоритм, то можно считать что это удаление и есть O(1). А бинпоиск - O(log n), как бы вы там не делили. Поэтому весь алгоритм с бинпоиском всегда будет медленнее, потому что там n шагов O(log n), а прямое удаление из стека состоит из n шагов O(1).
Если же у вас какая-то сильно другая задача, где вам надо online определять ближайший больший элемент и вам хочется иметь жесткое ограничение времени на каждый шаг, вот тогда вы можете применить бинпоиск, получив в итоге более вычислительно сложный алгоритм, но зато с гарантиями задержек на каждый запрос.
Я этот стек в прод коммитил. И на литкоде полно задач с ним. Так что может на интервью и попасться запросто.
Автор, вы когда задачи разбираете, если вы не объясняете логику (почему работает) и как до этого додуматься, никто не знающий решение и не поймет его. И на интервью сможет лишь воспроизвести по памяти и завалится на первом же вопросе. И придумать даже похожую задачу не сможет. А уже знающим решение ваша статья бесполезна.
И комментарии у вас в коде бесполезны. Они точно так же, как и статья, объясняют, что код делает, а не почему. Они его фактически повторяют. Ну видно же, что вы там считаете площадь и удаляете элемент из стека. Зачем вообще этот коммент? А почему площадь такая? Почему она считается при удалении?
В первой задаче вам надо добавить примерно такие рассуждения: вот мы хотим найти для каждого элемента массива ближайший справа больший его. Рассмотрим 2 соседних элемента (a[i] и a[i+1]). Если левый больше правого (a[i] >= a[i+1]), то правый никогда ни для какого числа левее не будет ответом. Потому что если a[i+1] > x, то и a[i] > x. Но индекс i ближе к x чем i+1, он же левее. Эту логику можно обобщить на любые два элемента a[i] >= a[j], i < j: для всех элементов левее a[i], a[j] никогда не будет ответом, потому что a[i] ближе.
Это ключевое наблюдение, на котором основана работа такого стека. Назовем элемент плохим, если он не может быть ни для кого ответом и хорошим наоборот. Так вот, в стеке хранятся как раз хорошие элементы. Вы добавляете элементы массива в рассмотрение по одному, удаляете те хорошие элементы, которые становятся плохими (из-за нового добавленного элемента). Ну и последний оставшийся в стеке будет ответом для нового числа. Потому что между ним и новым числом ничего больше нового нет (а если бы было, то оно осталось бы в стеке).
А вторая задача сводится к первой. Ключевое наблюдение - любой искомый прямоугольник ограничен по высоте каким-то конкретным столбцом, а по ширине идет влево и вправо до ближайшего столбца меньшего того "несущего". Иначе его можно увеличить по высоте или по ширине. Поэтому можно перебрать все столбцы в качестве "несущего", касающегося потолка прямоугольника, а дальше надо прямо как в первой задаче найти границы слева и справа - ближайшие слева и справа меньше текущего столбца. Это решение потребует двух стеков для ближайших меньших слева и справа (и два цикла вперед и назад). Вот, кстати, почему у вас в решении стек на возрастающие элементы, а не на убывающие, как в первой задаче - ведь тут ищутся ближайшие меньшие, а не больше, как в первой задаче.
Это решение можно дальше соптимизировать до одного стека и прохода, если понять, что ближайший справа будет тот, который вытесняет хороший элемент из стека. А ближайший слева - предыдущий в стеке. Поэтому вместо отдельно поиска двух горизонтальных границ, можно проверять ответ во время вытеснения элемента из стека.
Вот эти рассуждения объясняют ваше решение, а не "что если поддерживать монотонный стек".
Спасибо за отзыв!
По поводу первой задачи, действительно можно было бы дать подробное описание алгоритма. Вот только нужно ли это когда решение состоит по сути из цикла с 5 строчками кода внутри? Мне кажется код в данном случае выразительнее и большинство людей пропустили бы текстовое описание.
Во второй задаче, ваше ключевое наблюдение верно, но оно есть и в статье - первые два абзаца под спойлером, практически дословно. В остальном, мои рассуждения немного отличались, и главные "инсайты" я также постарался объяснить.
от только нужно ли это когда решение состоит по сути из цикла с 5 строчками кода внутри?
Нужно, потому что вообще непонятно откуда это берется, как и почему работает.
Представьте себе задачу, где можно применив кучу высшей математики вывести формулу n/2 и выдать это в ответ. И вы там еще, наверное, написали бы в объяснении, как у вас сейчас: "А что, если разделить n на 2?". И комментарий в коде вида "делим n на 2". И ни слова о том, как составить уравнения, как их решать, как прийти к формуле n/2.
Там вообще одна строчка кода будет, но пользы от такого разбора задачи вообще не будет. Если решение конкретно этой слово-в-слово задачи еще можно будет запомнить, как такой вот забавный интересный факт, то решить почти такую же задачу, где ответ будет уже n/4, прочитавшие ваш "разбор" не смогут.
По второй задаче: первый абзац действительно полезен, но дальше нет никаких рассуждений о том, откуда там берется стек, что на самом деле это сведение к первой задаче. Почему вы вообще "финализируете" прямоугольник именно там, где это происходит. Надо его переписать.
heights = [-2, -1, -5, -6, -2, -3] - решение 10, ваш алгоритм выдаёт 0. В целом изящное решение, не сразу понятно было, пришлось немного подумать, спасибо!
А тут запрещено идти с конца массива? В задаче с температурами можно пойти с конца и тогда на текущем элементе мы либо ставим 1, если он меньше впередидущего, либо по уже известным смещениям прыгаем к концу массива и находим ближайший больший без полного перебора. Такой вариант бы стал медленным o(n^2) для массива отсортированного в обратном порядке, а для произвольных массивов был бы наверное не сильно хуже n*log(n)
Это стоит рассмотреть лишь при отсутствии O(n) вспомогательной памяти, иначе выбор почти всегда делается в пользу скорости.
С конца идти не запрещено, конечно. Навскидку, такое решение это слегка оптимизированный брутфорс вариант, всё ещё за квадратичное время. Если интересно, попробуйте засабмитить его на leetcode, думаю не пройдёт по времени.
Ниже написал: Это тоже O(N) и там тоже есть монотонный стек (хоть и заныканный в ответе).
Если "по уже известным смещениям прыгаем к концу массива" реализовать с удалением неупорядоченных элементов, то да. Получается альтернативный вариант реализации через монотонный стек.
Какое удаление? Если "известное смещение" - это уже подсчитанный ответ к задаче, т.е. ссылка на ближайший справа строго больший элемент, то там не надо ничего удалять. неупорядоченные элементы пропускаются этими смещениями.
В этом случае в стеке будет возрастающая последовательность ранее встреченных температур. Если в стеке будет [8, 5, 3, 1] и вам встретилась температура 4, нужно будет удалить 1, 3, а 5 и 8 оставить в стеке. Если не удалять, получится решение за квадратичное время, как я написал выше. Если удалять, получится монотонный стек и решение за O(n)
Стек не храниться отдельно. Это просто последовательность достижимых по ссылкам с последнего обработанного элемента. Нет отдельного стека, есть только прыжки "по известным смещениям".
Вот есть массив [4,1,3,5,0,8]. Проходясь с конца вы подсчитали следующие для чисел 1,3,5,0,8, при этом ссылки будут на следующее большее. В стеке "храниться" [8,5,3,1], потому что от 1 идет ссылка в 3, от 3 ссылка в 5, от 5 - в 8.
Вот вам встретилась температура 4, и вы "пройдетесь по смещениям" к 1, потом к 3, потом к 5. И запишите в ответ, что для 4-ки следующая большая - вот на 5-ка. Теперь в "стеке" лежит [8,5,4]. Но ничего ниоткуда явно не удалялось. Просто поменялась голова стека.
Если же вы храните стек отдельно, то как вы вообще подумали как можно из стека не удалять ничего? Там тогда не будет возрастающей последовательности никак. Зачем там вообще стек?
Вот есть массив [4,1,3,5,0,8]. Проходясь с конца вы подсчитали следующие для чисел 1,3,5,0,8, при этом ссылки будут на следующее большее. В стеке "храниться" [8,5,3,1], потому что от 1 идет ссылка в 3, от 3 ссылка в 5, от 5 - в 8.
Вот вам встретилась температура 4, и вы "пройдетесь по смещениям" к 1, потом к 3, потом к 5. И запишите в ответ, что для 4-ки следующая большая - вот на 5-ка. Теперь в "стеке" лежит [8,5,4]. Но ничего ниоткуда явно не удалялось. Просто поменялась голова стека.
Вполне рабочий вариант, только со связным списком вместо монотонного стека )
Если же вы храните стек отдельно, то как вы вообще подумали как можно из стека не удалять ничего? Там тогда не будет возрастающей последовательности никак. Зачем там вообще стек?
Это вариант решения описанный LaRN. Удаления элементов там судя по всему нет, иначе бы не получилась сложность O(N^2) при массиве отсортированном в обратном порядке.
Это вариант решения описанный LaRN.
Я не так это понял. Единственная интерпретация "по известным смещениям прыгаем к концу" - это эти самые связные списки и есть.
Я вообще не могу себе представить хоть какой-то алгоритм, похожий на это, но без "удаления". Только наивный брутфорс, с проверкой всех элементов в хвосте. Но тут никакие смещения не используются же.
Вы предлагаете уже подсчичтанные ближайшие большие для следующих чисел использовать? Вроде, посмотрели следующий элемент, если он меньше, то берем ближайший справа больший, и так пока не дойдем до искомого или до конца массива?
Кстати, в упорядоченном по убыванию это будет O(N), ведь вы сразу видите, что больших там вообще нет и никуда итерироваться не надо.
Вообще, это будет тоже самое O(N), кстати. И тут такой же монотонный стек спрятан внутри.
Смотрите, этим стеком можно искать при проходе в любом направлении. Если вы идете слева-направо (и ищите ближайший справа строго больше), то вы в стеке поддерживаете нестрого убывающую последовательность, и при вытеснении элемента назначаете ему в ответ тот, который его вытесняет из стека. Автор в статье использует этот подход.
Если же вы идете справа-налево, то вы поддерживаете строго убывающую последовательность, и назначаете в ответ добавляемому в стек элементу оставшеюся верхушку в стеке. У вас эмулируется вот это вот.
В качестве "стека" будут те элементы, которые по ссылкам от последнего обработанного достижимы. Они будут строго возрастать, т.е. верхушка стека слева. При проходе по этим ссылкам вы фактически вытесняете элементы из стека, потому что текущий элемент станет последним обработанным и будет новой верхушкой стека и ссылка с него эти все элементы пропустит.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Монотонный стек: описание и примеры применения