Реализуйте стек, который кроме обычных операций умеет за O(1) возвращать максимальный
элемент. Это аналог Min Stack (LeetCode 155), только для максимума. Стек обобщённый
и работает с любым упорядоченным типом.
type MaxStack[T cmp.Ordered] struct{ /* ... */ }
func (s *MaxStack[T]) Push(x T)
func (s *MaxStack[T]) Pop() (T, bool) // снимает и возвращает вершину; false, если стек пуст
func (s *MaxStack[T]) Top() (T, bool) // вершина без снятия
func (s *MaxStack[T]) Max() (T, bool) // максимум среди всех элементов стека
func (s *MaxStack[T]) Len() int
Требования
- Все операции — O(1) (у
Push — амортизированно).
- Нулевое значение готово к работе:
var s MaxStack[int] без конструктора.
- На пустом стеке
Pop, Top, Max возвращают нулевое значение и false, без паники.
Пример
var s MaxStack[int]
s.Push(3)
s.Push(7)
s.Push(5)
s.Max() // 7, true
s.Pop() // 5, true
s.Pop() // 7, true
s.Max() // 3, true
Устно: как реализовать PopMax() — снять максимальный элемент из середины стека
(LeetCode 716)? Какая будет сложность?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.