Ctrl K

Башня, ниже которой с обеих сторон

Сложная
В ряд стоят башни, их высоты — массив heights. Дано положительное число k. Башня с индексом i **заметная**, если: - слева от неё есть хотя бы k башен строго ниже неё (индексы j < i с heights[j] < heights[i]); - справа от неё есть хотя бы k башен строго ниже неё (индексы j > i с heights[j] < heights[i]). Верните количество заметных башен.
Пример 1
heights=[1, 4, 2, 5, 3, 1], k=2 → 1

Башня высотой 5 (индекс 3): слева ниже неё 1, 4 и 2, справа — 3 и 1. Башня высотой 4 (индекс 1) не подходит: слева от неё лишь одна башня ниже.

Пример 2
heights=[2, 2, 2, 2], k=1 → 0

Равные башни не считаются более низкими, поэтому подходящих нет.

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

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