Сложность: medium
Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.
Пример:
Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]
👨💻 Алгоритм:
1⃣Инициализируйте цикл для добавления объема воды.
2⃣Для каждой единицы воды: Проверьте, может ли вода двигаться влево и упасть на более низкий уровень. Если нет, проверьте, может ли вода двигаться вправо и упасть на более низкий уровень. Если нет, добавьте воду в текущую позицию.
3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.
😎 Решение:
function pourWater($heights, $volume, $k) {
for ($v = 0; $v < $volume; $v++) {
$dropIndex = $k;
foreach ([-1, 1] as $d) {
$i = $k;
while ($i + $d >= 0 && $i + $d < count($heights) && $heights[$i + $d] <= $heights[$i]) {
if ($heights[$i + $d] < $heights[$i]) {
$dropIndex = $i + $d;
}
$i += $d;
}
if ($dropIndex != $k) {
break;
}
}
$heights[$dropIndex]++;
}
return $heights;
}Ставь 👍 и забирай 📚 Базу знаний