Поиск минимального значения в стеке с временной сложностью O (1)

Question

Как найти минимальное значение в стеке с сложностью O (1). Чтобы найти минимальное значение стека, я нашел два способа: 1) min = top значение стека Пройдите в стек и обновите значение min, чтобы получить минимальное значение стека. Это требует O (N) сложность, где N является количество элементов в стеке

2) Поместите элементы стека в minheap Корень значения, которые будут извлечены будет минимальное значение в стеке Это требует O (N log (N))

Но как реализовать алгоритм O (1), Алгоритм, который не зависит от размера ввода.

Здесь предположение, что стек уже загружен с элементами

Answer 1

Вы не можете. Алгоритм O (1) для поиска минимального элемента произвольного стека также может быть использован для нахождения минимального элемента дважды связанного списка, который затем можно использовать для создания алгоритма сортировки O (n).

Теперь можно реализовать стек, который отслеживает свой минимальный элемент по мере его создания. Такой стек мог бы вернуть свое сохраненное минимальное значение и только выполнить O (n) поиск, если вам удастся заполнить минимальный элемент. Но это не совсем то же самое.