как найти максимальное значение, хранящееся в стеке в постоянное время

Question

Использование временной переменной для хранения максимального значения не работает для операций pop.

Answer 1

Если вас не интересует O (n) в операции push:

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

Таким образом, у вас всегда должен быть самый высокий элемент в последнем элементе связанного списка, и время выталкивания составляет O (1).1006 * Если вам также нужен O (1) для толкания, тогда мне придется пройти.

Answer 2

Вы можете сделать это, управляя дополнительным стеком, который содержит максимумы.Алгоритм будет выглядеть так: при нажатии сравните новый элемент с вершиной стека максимумов.Если не меньше, то и там.После всплытия сравните элемент с вершиной стека максимумов.Если равный, вытолкните это оттуда также.В любой момент времени вершина стека максимумов является максимальным элементом.

Answer 3

Вы не можете. Стек не отсортирован, что означает, что вам нужно проверить все значения N, чтобы найти самое высокое. Это само по себе означает, что оно равно , по крайней мере, O (N), тогда как "постоянное время" означает O (1)