Premium

Массивы

Здания с видом на океан

Найти здания с видом на океан

Средний

Постановка задачи

Описание (LeetCode)

Вам дан массив целых чисел heights размера n, представляющих ряд зданий, где heights[i] это высота i-го здания.

Справа от всех зданий находится океан. Здание имеет вид на океан, если каждое здание справа от него строго меньше по высоте.

Верните список индексов (индексация с 0) зданий, которые имеют вид на океан, отсортированных в порядке возрастания.

Пример 1:

heights = [4, 2, 3, 1]

Результат:

[0, 2, 3]

Пояснение:

  • Здание 0 имеет вид на океан, так как нет зданий выше справа от него.
  • Здание 2 имеет вид на океан, так как здание 3 ниже.
  • Здание 3 всегда имеет вид на океан.

Пример 2:

heights = [4, 3, 2, 1]

Результат:

[0, 1, 2, 3]

Пояснение:

Все здания имеют вид на океан.

Пример 3:

heights = [1, 3, 2, 4]

Результат:

[3]

Пояснение:

Только здание 3 имеет вид на океан.

Ограничения:

  • 1 <= heights.length <= 10⁵
  • 1 <= heights[i] <= 10⁹

Решение

"Здания с видом на океан" - задача среднего уровня, которая хорошо иллюстрирует идею из предыдущей задачи. Хотя здесь говорится о "зданиях", суть в том, что нам нужна фильтрация доминирующих элементов, справа от которых все элементы строго меньше. Такая задача может встретиться на практике в разных "обертках", например:

  1. Обработка сигналов. При анализе звуковых волн нужно выделять пиковые амплитуды, которые не заглушаются последующим шумом. Например, при сжатии данных мы можем игнорировать "слабые" сигналы, которые следуют сразу за "сильными", если они не несут полезной информации.
  2. Пользовательские интерфейсы. Представим себе систему уведомлений или всплывающих окон с разным приоритетом. Каждое новое уведомление должно "перекрывать" старые и нам нужно вычислить, какие элементы интерфейса останутся видимыми для пользователя, а какие окажутся закрыты.
  3. Логистика. Например, если есть конвейер с коробками разной высоты и сканер в конце, нужно определить, какие коробки будут "видны" сканеру, чтобы правильно настроить систему автоматической сортировки.

В подобных задачах нужен поиск максимумов в последовательности и эффективная (за один проход) фильтрация данных, которая бы отсекала лишние элементы.

Наивное решение (полным перебором) заключается в том, чтобы для каждого здания честно проверить все здания, стоящие справа от него:

  • Берем здание с индексом i.
  • Запускаем второй цикл, который смотрит на все здания от i + 1 до самого конца.
  • Если мы находим хотя бы одно здание, которое выше или равно текущему, значит, вида на океан нет.
  • Если мы дошли до конца и не встретили ничего выше - добавляем индекс i в ответ.

В таком решении мы получим сложность O(n²), что неэффективно для больших массивов.

Давайте найдем более оптимальный подход, опираясь на идею из предыдущей задачи.

Здесь мы видим, что результат для i-го здания явно зависит от высот его правых соседей. Поэтому задаем себе вопрос: "А может быть здесь лучше пойти с конца массива?"

И действительно, это самый простой способ: идти с конца, от океана, и запоминать максимальную высоту, которую мы встретили на данный момент. Таким образом мы будем для текущего i-го здания сразу знать, есть ли у него вид на океан или нет.

Таким образом, алгоритм заключается в том, чтобы двигаться справа налево, сохраняя значение самого большого встреченного элемента.

Основные шаги:

  1. Создаем пустой список для результатов res и переменную maxHeight = -1.
  2. Идем по массиву с конца к началу:
    • Если текущее здание выше maxHeight, значит, оно видит океан. Добавляем его индекс в res.
    • Обновляем maxHeight, если текущее здание выше.
  3. Переворачиваем res в конце, так как мы шли справа.

После обсуждения идеи решения надо прогнать его на примерах вручную. Проверьте решение самостоятельно на примерах и убедитесь, что алгоритм дает верные ответы.

Оценка сложности

Временная сложность

Это решение имеет линейную сложность: O(n), так как мы проходим по массиву ровно один раз с конца с помощью одного цикла.

Пространственная сложность

Мы используем дополнительный массив для результата, поэтому по памяти у нас также линейная сложность: O(n).

Код решения

Теперь можем написать код решения.

func findBuildings(heights []int) []int {
    var res []int
    maxHeight := -1
    for i := len(heights) - 1; i >= 0; i-- {
        if heights[i] > maxHeight {
            res = append(res, i)
            maxHeight = heights[i]
        }
    }
    for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
        res[i], res[j] = res[j], res[i]
    }
    return res
}

Итоги

В ходе разбора задачи мы перешли от интуитивного, но медленного подхода к оптимальному алгоритму, используя паттерн проход с конца.

Проход с конца очень прост и делает решение этой задачи действительно простым. Также существует решение с использованием монотонного стека - это более универсальный паттерн, который часто встречается в алгоритмических задачах и мы подробно рассмотрим его в будущих главах.

Выводы:

  1. Идея решения. Проход справа налево является "золотым стандартом" для этой задачи.
  2. Эффективность. Это классический пример того, как простая идея обхода массива превращает тяжелое решение O(n²) в максимально легкое O(n).
  3. Строгое условие. Здание должно быть строго выше тех, что справа. Поэтому мы обновляем результат только если heights[i] > maxHeight. Если высоты равны, левое здание океан не видит.
  4. Порядок индексов. Так как мы идем с конца, индексы в результирующем массиве окажутся в убывающем порядке. Нужно не забыть развернуть массив перед возвратом, чтобы соблюсти требования.
Войдите чтобы отмечать прогресс