Ctrl K

Отрезки, обрамлённые вершинами

Сложная
Вдоль горного хребта отмечены точки, их высоты записаны в массив heights в порядке следования. Назовём непрерывный отрезок heights[l..r] (где l ≤ r) удачным, если его первая и последняя точки обе имеют наибольшую высоту на этом отрезке. Иначе говоря, heights[l] == heights[r], и между ними нет точки выше. Верните количество удачных отрезков. Отрезок из одной точки тоже считается.
Пример 1
heights=[2, 5, 1, 5, 3] → 6

Подходят все 5 отрезков из одной точки и ещё [5, 1, 5]: оба края равны 5, и выше ничего нет. Итого 6.

Пример 2
heights=[4, 4, 4] → 6

Подходит любой из 6 отрезков: все высоты одинаковые.

Пример 3
heights=[3, 7, 3] → 3

Отрезок [3, 7, 3] не подходит — внутри есть вершина 7 выше краёв. Остаются только 3 отрезка из одной точки.

Ограничения
  • 1 ≤ len(heights) ≤ 10⁵
  • 1 ≤ heights[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиШирокий отрезок забора вокруг метки СложнаяВторое большее справа СложнаяЛучшая пара выше планок СложнаяПервая общая крыша СложнаяБольше всего блоков после слияний Сложная
загружаем Python…
Вход
heights=[2, 5, 1, 5, 3]
Ожидается
6

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 113 тестов на сервере, включая скрытые.