Сложность: medium
Вам дан целочисленный массив target и целое число n.
У вас есть пустой стек с двумя следующими операциями:
"Push": добавляет целое число на вершину стека.
"Pop": удаляет целое число с вершины стека.
Также у вас есть поток целых чисел в диапазоне [1, n].
Используйте две операции стека, чтобы сделать числа в стеке (от нижнего к верхнему) равными target. Вы должны следовать следующим правилам:
Если поток чисел не пуст, возьмите следующее целое число из потока и поместите его на вершину стека.
Если стек не пуст, извлеките целое число с вершины стека.
Если в любой момент элементы в стеке (от нижнего к верхнему) равны target, не берите новые числа из потока и не выполняйте больше операций со стеком.
Верните операции стека, необходимые для построения target согласно указанным правилам. Если существует несколько правильных ответов, верните любой из них.
Пример:
Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].
👨💻 Алгоритм:
1⃣Инициализировать пустой список ans и переменную i равной 0.
2⃣Для каждого элемента num в target:
Пока i < num - 1:
Добавить "Push" в ans.
Добавить "Pop" в ans.
Увеличить i.
Добавить "Push" в ans.
Увеличить i.
3⃣Вернуть ans.
😎 Решение:
class Solution:
def buildArray(self, target: List[int], n: int) -> List[str]:
ans = []
i = 0
for num in target:
while i < num - 1:
ans.append("Push")
ans.append("Pop")
i += 1
ans.append("Push")
i += 1
return ans
Ставь 👍 и забирай 📚 Базу знаний