Для массива проверка монотонности требует O(n) в худшем случае и O(1) памяти. Можно сделать один проход с ранним выходом, но асимптотически лучше обычно нельзя.
Можно ли оптимизировать алгоритм проверки монотонности?
Для массива проверка монотонности требует O(n) в худшем случае и O(1) памяти. Можно сделать один проход с ранним выходом, но асимптотически лучше обычно нельзя.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Для массива проверка монотонности требует O(n) в худшем случае и O(1) памяти. Можно сделать один проход с ранним выходом, но асимптотически лучше обычно нельзя.
Храните признаки допустимости неубывания и невозрастания; при каждой соседней паре снимайте нарушенный признак. Когда оба ложны, сразу верните false. Равные элементы не нарушают нестрогую монотонность, пустой и одноэлементный массив подходят. В худшем случае последний элемент меняет ответ, поэтому нужно проверить весь массив; для строгой монотонности правило равенства другое.