Linkedlist отслеживает мин в постоянном времени?

РЕДАКТИРОВАТЬ:

Это не так тривиально, как ты думаешь.Учтите, что каждый добавление нового числа выталкивает старый номер из связанного списка.

Решение не похоже на просто, как отслеживать мин число с переменной. Что, если минимум выталкивается из связанный список? И что? Откуда вы знаете какой новый мин?

Я слышал этот вопрос из интервью:

У вас есть связанный список фиксированной длины.

• В момент времени t = 0 связанный список заполняется со случайными числами.

• При каждом приращении времени один новый номер подается в голову связанный список, и один номер помещается из хвоста.

• Вам разрешен только ОДИН обход до первого временного интервала.

  • Это означает один обход за все время. Не один раз в каждый момент времени t.
    .

• O (1) хранилище.

Ваша задача - иметь возможность возвращать минимальное значение связанного списка при каждом взаимодействии.

Какой алгоритм может это сделать?

Интересное примечание:

Поскольку нет информации относительно временная сложность, вы можете использовать операции сортировки. Единственная проблема в этом случае: для сортировки требуется более одной итерации.