MiddleКодИногдаЕщё не отвечали
Самый длинный строго монотонный подотрезок за O(n)
Дан массив целых. Найдите самый длинный строго возрастающий ИЛИ строго убывающий непрерывный подотрезок и верните его индексы [start, end]. Для [2,7,5,4,3] ответ — серия 7,5,4,3 на индексах [1,4].
Требования:
- O(n) по времени, O(1) доп. памяти; вход не менять.
std::pair<int,int> longestMonotoneRun(const std::vector<int>& a) {
// ваш код здесь
}Допишите реализацию.
Один проход с отслеживанием начала и направления текущей серии. Если следующая пара меняет направление — начните серию с предыдущего индекса; если равна — с текущего. Храните самую длинную серию. Равенство всегда обрывает строгую серию. O(n) время, O(1) память.
- ✗Считать равные соседние значения продолжением строго монотонной серии
- ✗Сбрасывать начало серии на текущий индекс вместо предыдущего при смене направления
- ✗Ошибка на единицу, когда самая длинная серия кончается последним элементом
- →Почему новая серия начинается с предыдущего индекса, а не с текущего?
- →Как изменится логика для нестрогой (с равенством) монотонности?
Оглавление
Задача
Найдите самый длинный строго монотонный подотрезок за один проход.
Решение
#include <vector>
#include <utility>
std::pair<int,int> longestMonotoneRun(const std::vector<int>& a) {
if (a.empty()) return {-1, -1};
int bestStart = 0, bestEnd = 0, runStart = 0;
int dir = 0; // +1 вверх, -1 вниз, 0 неизвестно
for (int i = 1; i < static_cast<int>(a.size()); ++i) {
int d = (a[i] > a[i-1]) - (a[i] < a[i-1]); // -1/0/+1
if (d == 0 || (dir != 0 && d != dir)) {
runStart = (d == 0) ? i : i - 1; // равенство рвёт строго
dir = d;
} else {
dir = d;
}
if (i - runStart > bestEnd - bestStart) { bestStart = runStart; bestEnd = i; }
}
return {bestStart, bestEnd};
}Ключевые моменты
- Одно сканирование с направлением серии; смена или равенство сбрасывают её.
- При смене направления новая серия начинается с предыдущего индекса.
- Равенство обрывает строгую монотонность.
Оглавление
