Определите, является ли слайс целых монотонным, за O(n)
Реализуйте isMonotonic(in), возвращающую true, если слайс монотонный — либо везде неубывающий, либо везде невозрастающий. Требование: один проход, O(n) по времени, O(1) доп. памяти. Примеры: {1,7} → true; {1,1} → true; {3,3,1} → true; {9,5,1} → true; {23,5,23} → false.
func isMonotonic(in []int) bool {
// ваш код здесь
return false
}Допишите реализацию.
Держите два булевых флага, isUp и isDown, оба истинны в начале. Пройдите по соседним парам один раз: оставляйте isUp истинным, пока in[i-1] <= in[i], а isDown — пока in[i-1] >= in[i]. Верните isUp || isDown. Ровный участок держит оба истинными, а смена направления гасит один. Это O(n) по времени, O(1) по памяти, один проход.
- ✗Фиксировать направление по первой паре вместо отслеживания обоих флагов
- ✗Считать равные соседние элементы нарушением монотонности
- ✗Решать только по концам, пропуская провал в середине
- →Как изменить, чтобы требовать строгую монотонность (без равных соседей)?
- →Можно ли выйти досрочно, как только оба флага станут ложными?
Решение
Два флага сразу учитывают обе допустимые тенденции. Ни одного перевыделения и сортировки.
func isMonotonic(in []int) bool {
isUp, isDown := true, true
for i := 1; i < len(in); i++ {
isDown = isDown && in[i-1] >= in[i]
isUp = isUp && in[i-1] <= in[i]
}
return isUp || isDown
}
// {3,3,1} -> true {23,5,23} -> falseisUp остаётся истинным, пока последовательность не убывает; isDown — пока не возрастает. Равные соседи (>= и <= нестрогие) держат оба флага, поэтому {1,1} и {3,3,1} монотонны. Если есть и подъём, и спуск, оба флага гаснут и результат false.
⚠️ Решать только по in[0] и in[len-1] неверно: {1,5,1} имеет равные концы, но не монотонен.
