Сяо Хуэй вспомнил сцену того времени...
тема:Реализуйте стек с тремя методами: pop, push и getMin. Необходимо убедиться, что временная сложность этих трех методов равна O(1).
Мысли Эша:
1. Создайте целочисленную переменную min с начальным значением -1.
2. Когда первый элемент помещается в стек, пусть min=0, то есть единственный элемент рассматривается как минимальное значение.
3. После этого всякий раз, когда новый элемент находится вблизи стека, сравните размер нового элемента с элементом, направленным на мин. Если стек [мин] больше, чем новый элемент, мин равна индексу нового элемента; если стек [мин] меньше, чем новый элемент, изменение не сделано.
4. Когда требуется метод Getmin, элемент непосредственно возвращается в положение, указанное на местоположение.
Согласно этой идее, временная сложность подхода к стеку, извлечения из стека и взятия минимального значения составляет O(1), а пространственная сложность также равна O(1).
На этом память заканчивается...
решение:
1. Пусть исходный стек называется стек A. В это время создается дополнительный стек B, чтобы помочь исходному стеку A.
2. Когда первый элемент входит в стек A, пусть нижний индекс нового элемента входит в стек B. Этот единственный элемент является текущим минимальным значением стека A. (Учитывая, что элементы в стеке могут не быть объектами класса, в стеке B хранится индекс элемента стека A)
3. Всякий раз, когда новый элемент входит в стек A, сравнивается размер нового элемента и текущего минимума стека A. Если он меньше текущего минимума стека A, позвольте новым элементам войти в стек B, в это время верхний элемент стека B Это заголовок текущего наименьшего значения.
4. Всякий раз, когда элемент выскочит из стека A, если выскоковый элемент является текущим минимальным значением стека A, верхний элемент стека B также выскочит из стека. В это время оставшийся верхний элемент стека B указывает на второй маленький элемент в стеке A, который становится текущим минимальным значением стека a вместо ранее выскоченного элемента. (Запасная шина получила положитель)
5. При вызове метода getMin просто верните соответствующий элемент стека A, на который указывает вершина стека B.
Временная сложность подхода к стеку, извлечения из стека и получения минимального значения в этом решении составляет O (1), а пространственная сложность в наихудшем случае — O (N).
Расширенная тема:
Реализуйте очередь с тремя методами: dequeue (deQueue), enqueue (enQueue) и возьмите наименьший элемент (getMin). Чтобы временная сложность этих трех методов была как можно меньше.
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента