Введение
Если вы инженер, готовящийся к техническим собеседованиям, скорее всего, вам нужно будет знать, как реализовать стек. В этом блоге я собираюсь научить вас решать распространенный вопрос о leetcode под названием Min Stack, который, надеюсь, сделает реализацию стека менее чуждой вам. Min Stack - довольно простой вопрос, но если вы не понимаете, что за ним стоит, вы можете не справиться с другими вопросами, связанными со стеками. Поэтому важно повторить этот вопрос несколько раз, пока вы не будете готовы ответить на другие вопросы, связанные со стеком.
Вот ссылка на вопрос, чтобы вы могли следить за ним.
Быстрая справка по стопкам
Стек - это линейная структура данных, похожая на массив, с той разницей, что вы можете вставлять и удалять элементы только с его конца. Стопку можно рассматривать как стопку тяжелых книг. Если вы хотите добавить в эту стопку книг, скорее всего, вы положили бы следующую книгу сверху, а если бы вы хотели удалить книгу из стопки, вы, вероятно, удалили бы ту, которую только что добавили. Этот принцип называется FIFO или First In First Out, и именно он делает стеки уникальными. Хотя стеки могут показаться ограничивающими, они хороши тем, что вставка и удаление теперь имеют пространственно-временную сложность O (1).
Концептуальное решение вопроса
Теперь, когда у вас есть базовое представление о стеках, пора учиться на практике. Вопрос о минимальном стеке просит нас просто реализовать стек с четырьмя разными методами. Первые три являются общими для большинства реализаций стека, это push (), pop () и top (). Если вы раньше использовали массив JavaScript, вы, вероятно, хорошо знакомы с первыми двумя методами. Третий метод - это просто способ взглянуть на последний элемент в стеке, его также можно вызвать peek (). Однако последний метод, который они хотят, чтобы мы реализовали, составляет суть вопроса. Это метод getMin (). Этот метод должен возвращать минимальный элемент из стека за постоянное время.
Это означает, что мы не можем просто перебрать вопрос и реализовать цикл для его решения. Вместо этого мы должны использовать сильные стороны стека. Как вы знаете, стек очень хорош для доступа, удаления и вставки последнего элемента в себе. Итак, чтобы отслеживать минимум, нам нужно, чтобы наименьшее значение находилось на вершине стека. Способ сделать это - реализовать два стека, один из которых содержит каждое значение, а другой - только минимальные значения. Это может немного сбить с толку, но, надеюсь, после его реализации вы лучше поймете эту идею.
Решение вопроса с помощью JavaScript
Первое, что нам нужно сделать, это создать наш класс MinStack. Мы сделаем это, инициализировав объект двумя массивами с именами stack и minstack. Однако перед этим нам понадобится вспомогательная функция, которая имеет доступ к последнему элементу в стеке. Я рекомендую написать этот помощник для большинства вопросов о стеке, поскольку нам, скорее всего, придется что-то делать с последним элементом.
Теперь реализуем метод push () так:
Здесь мы помещаем все в основной стек, но мы также помещаем самый последний минимум в минимальный стек. Это сделает так, что последний элемент минимального стека всегда будет минимальным из нашего основного стека.
Далее мы захотим реализовать pop () аналогичным образом:
Здесь мы извлекаем все из основного стека, но если элемент является минимальным, мы также извлекаем его из нашего минимального стека.
Теперь все, что нам нужно сделать для следующих методов буксировки, - это взять последний элемент из основного стека и минимальный стек соответственно следующим образом:
Окончательный код
function last(stack){
return stack[stack.length - 1]
}
class MinStack {
constructor(){
this.stack = []
this.minStack = []
}
push(x){
if(this.minStack.length === 0 || x <= last(this.minStack)){
this.minStack.push(x)
}
this.stack.push(x)
}
pop(){
if(last(this.minStack) === last(this.stack)){
this.minStack.pop()
}
return this.stack.pop()
}
top(){
return last(this.stack)
}
getMin(){
return last(this.minStack)
}
}
Заключение
И это все! Вот как вы решаете вопрос о минимальном стеке за постоянное время. Спасибо за чтение!
Источники:
