Ctrl K

Широкий отрезок забора вокруг метки

Сложная
Забор состоит из досок высотой heights[0], heights[1], …. Доска с номером anchor помечена. Выберите отрезок подряд идущих досок с i по j, в который входит помеченная доска (i ≤ anchor ≤ j). Его ценность — высота самой низкой доски отрезка, умноженная на количество досок: min(heights[i..j]) · (j − i + 1). Верните наибольшую ценность такого отрезка.
Пример 1
heights=[2, 6, 5, 8, 1], anchor=2 → 15

Отрезок с 1-й по 3-ю доску: самая низкая — 5, досок три, 5 × 3 = 15. Если добавить доску высотой 2 или 1, высота упадёт сильнее, чем вырастет ширина.

Пример 2
heights=[3, 3, 3, 3], anchor=0 → 12

Все доски одинаковые, берём весь забор: 3 × 4 = 12.

Пример 3
heights=[1, 9, 1], anchor=1 → 9

Доска 9 одна даёт 9, а с соседями — только 1 × 3 = 3.

Ограничения
  • 1 ≤ heights.length ≤ 10⁵
  • 1 ≤ heights[i] ≤ 2 · 10⁴
  • 0 ≤ anchor < heights.length
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВырезать кусок ради порядка СредняяВода между стенами СложнаяНаибольшее число из двух рядов СложнаяВторое большее справа СложнаяЛучшая пара выше планок Сложная
загружаем Python…
Вход
heights=[2, 6, 5, 8, 1], anchor=2
Ожидается
15

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