Daily bit(e) C++. Удержанная вода

Добавлено 3 августа 2023 в 20:51

Daily bit(e) of C++ #2, распространенные вопросы на интервью: удержанная вода.

Сегодня мы рассмотрим распространенный вопрос на собеседованиях – «удержанная вода».

Дана одномерная карта высот местности (например, [0, 2, 3, 0, 2, 0]), определите общее количество воды, которое будет улавливаться этой местностью.

Для приведенного выше примера это будут два блока воды.

Прежде чем прочитать решение, попробуйте решить задачу самостоятельно. Вот ссылка Compiler Explorer с несколькими тестовыми случаями: https://godbolt.org/z/hKx7773qM.

Решение

Во-первых, давайте проанализируем задачу. Когда вода остается в определенном пространстве? Вода попадает в ловушку, когда на этой высоте где-то слева и справа от нее есть рельеф.

Мы можем расширить эту идею, чтобы определить высоту воды в определенной координате. Максимальная высота воды – это максимальная высота рельефа слева и справа.

Фактическая высота воды равна этому максимуму минус высота местности в этом месте.

Итак, для расчета нам нужно перебрать все пробелы на карте высот, вычислив min(left_max, right_max)-terrain.

Мы можем вычислить left_max при обходе местности, однако нам необходимо предварительно вычислить right_max.

К счастью, у нас есть готовый алгоритм, который может сделать это за нас. Мы можем использовать std::inclusive_scan с std::max в качестве операции сокращения. Наконец, поскольку эти значения нужно вычислять справа налево, нам нужно использовать обратные итераторы.

int trapped_water(const std::vector<int>& terrain) 
{
    // предварительный расчет right_max
    std::vector<int> right_max(terrain.size());
    // справа налево с использованием обратных итераторов
    std::inclusive_scan(terrain.rbegin(), terrain.rend(), 
        right_max.rbegin(),
        [](int l, int r) { return std::max(l, r); });
    // Это сгенерирует: first, max(first, second), 
    // max(max(first, second), third)...

    int left_max = 0;
    int water = 0;
    // теперь идем слева направо
    for (auto idx : std::views::iota(0uz, terrain.size())) 
    {
        // по ходу следим за левым максимумом
        left_max = std::max(left_max, terrain[idx]);
        // Рассчитываем уровень воды в этом месте,
        // это значение не может быть отрицательным из-за inclusive_scan
        water += std::min(left_max, right_max[idx]) - terrain[idx];
    }

    return water;
}

Открыть решение на Compiler Explorer.

Решение

Теги