➡️ Стартуем тему стека

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

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

#stack

🟢Easy
1047. Remove All Adjacent Duplicates In String

Company: 🏢🔍📱

📝Вам дана строка s, состоящая из строчных английских букв. Удаляйте соседние одинаковые буквы, пока это возможно.

Верните окончательную строку после всех удалений

💡: сравнивайте текущий символ с верхним в стеке

#leetcode1047 | #easy #stack

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

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

💡 Идея
🟦инициализируем стек для отслеживания пар и StringBuilder для финального ответа

🟦проходим по строке и на каждом шаге проверяем:

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

➖иначе добавляем текущий символ в стек

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

👩‍💻 Java Algo | #solution1047

🟢Easy
1475. Final Prices With a Special Discount in a Shop

Company: 🔍📱🏢

📝Дан целочисленный массив prices, где prices[i] — цена товара в магазине.

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

Верните массив result, где result[i] — окончательная цена, которую вы заплатите за товар в магазине с учетом специальной скидки

💡: поддерживайте в стеке индексы элементов, для которых пока не найдена скидка

#leetcode1475 | #easy #stack

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

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

💡 Идея

➖для каждого элемента наш стек должен содержать все самые последние цены перед этим элементом, которые больше него. Это означает, что все элементы в стеке находятся в порядке возрастания, что называется монотонным стеком

🟦инициализируем стек индексов цен, поскольку нам нужны позиции для применения скидок, и массив results (с копией значений prices) для записи ответа

🟦проходим по исходному массиву и проверяем, что текущий элемент меньше или равен верхней цене в стеке

🟦если это так, используем текущий элемент в качестве скидки для всех элементов под индексами, которые мы сохранили в стеке:
▫извлекаем индексы из стека, пока он не опустеет или верхняя цена не станет меньше текущей, уменьшая соответствующую ячейку в results

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

👩‍💻 Java Algo | #solution1475

🟡Medium
227. Basic Calculator II

Company: 🏢📱🚀

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

💡: вычисляйте промежуточные значения, используя предыдущую операцию, и складывайте их в стек

#leetcode227 | #medium #stack

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

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

💡 Идея
🟦проходим по строке:
➖если встречаем цифру, строим текущее число, так как оно может быть многозначное
➖если встречаем оператор или находимся в конце строки, выполняем операцию с текущим числом, используя предыдущий оператор:

▫'+' — просто добавляем текущее число в стек
▫'-' — добавляем в стек текущее число с минусом
▫'*' — умножаем последнее число в стеке на текущее и добавляем полученное значение в стек
▫'/' — делим последнее число в стеке на текущее и добавляем полученное значение в стек
▫после этого обновляем prevOp на текущий оператор и обнуляем текущее число для формирования следующего

🟦в конце просто суммируем все элементы в стеке, так как умножение и деление мы выполняли сразу, тем самым учитывая приоритет операций

👩‍💻 Java Algo | #solution227

🟡Medium
1209. Remove All Adjacent Duplicates in String II

Company: 🏢📱📱

📝Дана строка s и целое число k. Удаляйте из строки группы из k одинаковых подряд идущих символов, пока это возможно.

Верните итоговую строку после всех удалений

💡: храните в стеке количество подряд идущих одинаковых символов

#leetcode1209 | #medium #stack

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

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

💡 Идея
🟦инициализируем стек для хранения кол-ва подряд идущих одинаковых букв, массив символов res из исходной строки, чтобы можно было ее изменять, а также указатель j для обозначения текущей позиции финальной строки

🟦проходим по исходной строке двумя указателями (i и j) и на каждом шаге:
▫копируем в res[j] символ под указателем i

▫если текущий символ под указателем j не равен предыдущему, кладем в стек 1, иначе достаем из стека верхнее значение, увеличиваем его, а затем проверяем:

➖если новое значение равно k, уменьшаем указатель j на k, тем самым удаляя последние k символов
➖иначе просто кладем в стек новое значение

🟦в конце формируем итоговую строку из массива res, указывая границы: new String(res, 0, j)

👩‍💻 Java Algo | #solution1209

🟡Medium
1673. Find the Most Competitive Subsequence

Company: 🔍🚖

📝Дан массив целых чисел nums и положительное целое число k, вернуть наиболее конкурентоспособную подпоследовательность nums размера k.

Подпоследовательность A более конкурентоспособна, чем подпоследовательность B, если в первой позиции, где A и B различаются, подпоследовательность A имеет меньшее число.

Например, [1, 3, 4] более конкурентоспособна, чем [1, 3, 5]

💡: поддерживайте монотонный стек с минимальными числами в начале

#leetcode1673 | #medium #stack

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

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

💡 Идея

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

🟦проходим по массиву и на каждом шаге:
➖в начале определяем количество оставшихся элементов до конца массива, включая текущий

➖затем убираем элементы из стека, пока верхний больше, чем текущий и, пока количество оставшихся элементов в массиве больше, чем свободного места в стеке до длины k

➖добавляем текущий элемент в стек, если его размер меньше k

🟦в конце перебираем все элементы стека и записываем в массив ответа

👩‍💻 Java Algo | #solution1673

🟡Medium
456. 132 Pattern

Company: 📱🏢🅰️

📝Дан массив целых чисел nums. Шаблон 132 представляет собой подпоследовательность из трех целых чисел nums[i], nums[j], nums[k], где i < j < k и nums[i] < nums[k] < nums[j]

Верните true, если в массиве есть шаблон 132

💡: для поиска элементов j и k используйте монотонный стек, а для элемента i подготовьте массив минимумов

#leetcode456 | #medium #stack

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

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

💡 Идея
🟦Для поиска элементов j и k будем поддерживать монотонный стек, в котором все элементы идут в убывающем порядке. Поэтому в тот момент, когда наш стек не пуст, у нас всегда есть две найденные позиции, для которых выполняется условие nums[k] < nums[j]

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

🟦В итоге получаем следующий алгоритм на каждом шаге прохода по массиву:

1⃣Удаляем элементы из стека, пока он не пуст и его верхний элемент меньше или равен текущему

2⃣Проверяем главное условие nums[i] < nums[k] < nums[j]:
▫стек не пуст — значит в нем сейчас содержится элемент j, а текущий является k
▫минимальный элемент слева от индекса j меньше текущего элемента k (ищем элемент i)

3⃣Добавляем индекс текущего элемента в стек

👩‍💻 Java Algo | #solution456

🔴Hard
1106. Parsing A Boolean Expression

Company: 📱🔍🏢

📝Дана строка expression, представляющая логическое выражение, необходимо вернуть его результат.

Выражение состоит из:
▫'t' — true
▫'f' — false
▫'!(subExpr)' — логическое НЕ внутреннего выражения subExpr
▫'&(subExpr1, subExpr2, ...)' — логическое И внутренних выражений
▫'|(subExpr1, subExpr2, ...)' — логическое ИЛИ внутренних выражений

💡: складывайте в стек операторы и булевые значения, а при встрече ')' сразу обрабатывайте подвыражение

#leetcode1106 | #hard #stack

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

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

💡 Идея
🟦проходим по строке и кладем в стек только значимые элементы: операторы и булевые значения, пропуская все открывающиеся скобки и запятые

🟦если встретили ')', это знак, что пора обрабатывать внутреннее выражение:
➖достаем из стека все булевые значения, пока не встретили оператор, при этом помечаем — было ли хотя бы одно true или false

➖затем вычисляем подвыражение:
▫если оператор '&', ответ true, только, если не было false
▫если оператор '|', ответ true, если было хотя бы одно true
▫если оператор '!', переворачиваем булевое значение

🟦после полной обработки строки, в стеке остается только один символ — результат всего выражения, возвращаем true, если это 't'

👩‍💻 Java Algo | #solution1106

🔴Hard
1944. Number of Visible People in a Queue

Company: 🔍📱🏢

📝Вам дан массив heights различных целых чисел, где heights[i] представляет собой рост человека, стоящего на позиции i.

Человек может видеть другого человека справа от себя, если все люди между ними имеют меньший рост, чем и он сам, и тот, кого он видит.

Верните массив result, где result[i] — количество людей, которых человек на позиции i может видеть справа от себя

💡: заполняйте стек с конца, поддерживая убывающий порядок

#leetcode1944 | #hard #stack

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

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

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

🟦для этого удобно использовать монотонный стек, но если двигаться слева направо, то пришлось бы для каждого элемента пересчитывать его заново, и мы получили бы сложность O(n²)

🟦поэтому проходим исходный массив с конца, поддерживая убывающий стек:

➖для каждого элемента сначала удаляем с вершины стека все элементы, которые меньше него, одновременно считая их количество

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

➖затем добавляем текущий индекс в стек

👩‍💻 Java Algo | #solution1944

🔴Hard
768. Max Chunks To Make Sorted II

Company: 📱📱🔍

📝Дан массив целых чисел.

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

Найдите максимальное количество таких фрагментов, при котором выполняется условие

💡: храните в стеке максимумы предыдущих фрагментов, а максимум для текущего храните в переменной

#leetcode768 | #hard #stack

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

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

💡 Идея
🟦заметим, что минимальный элемент текущего фрагмента должен быть больше или равен максимуму предыдущего, тогда после сортировки все фрагменты образуют верный массив

🟦используем стек для отслеживания границ потенциальных фрагментов, в котором будем хранить их максимумы. Текущий максимум храним в переменной currMax, которую используем для понимания, можно ли начать новый фрагмент

🟦в итоге получаем следующий алгоритм на каждом шаге прохода по массиву:

➖пока текущий элемент меньше вершины стека, то есть он нарушает условие порядка фрагментов, мы удаляем элементы из стека (расширяем предыдущий фрагмент)

➖если текущий элемент больше или равен текущему максимуму, значит мы можем начать новый фрагмент:
▫кладем в стек currMax и обновляем его на текущий элемент

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

👩‍💻 Java Algo | #solution768