Освітлені будівлі#148

Освітлені будівлі (Розбір)

Ліхтар світить збоку першої будівлі, промені паралельні землі. Будівля освітлена, якщо хоч частина її стіни не затулена — а затуляють її лише будівлі, що стоять перед нею.

Отже, будівля освітлена тоді й лише тоді, коли її висота строго більша за висоти всіх попередніх:

H_i > \max(H_1, H_2, \ldots, H_{i-1}).

Якщо знайдеться попередня будівля такої ж або більшої висоти, вона повністю перекриє промені, і жодного вільного метра стіни не залишиться.

Звідси розв'язок в один прохід: тримаємо поточний максимум висоти (спочатку ), для кожної будівлі порівнюємо її висоту з максимумом і, якщо вона більша, збільшуємо відповідь та оновлюємо максимум.

Перша будівля освітлена завжди, бо перед нею нічого немає, — початкове значення максимуму забезпечує це автоматично, адже H_i \ge 1.

Складність — , зберігати весь масив навіть не обов'язково.