— перебор, динамическое программирование, два указателя
Вопрос
- Индекс может задерживать воду только при наличии полос (более высоких значений) с обеих сторон, поэтому первый и последний индекс никогда не могут задерживать воду.
- От нижней планки зависит, сколько воды может быть уловлено.
Грубая сила
Так как первый и последний индекс никогда не могут задерживать воду, мы можем перебирать массив от индекса 1 до индекса arr.length-2.
По каждому индексу current мы проверяем левую часть индекса current от индекса 0 до индекса current-1, чтобы найти максимальное значение leftMax.
И мы проверяем правую часть текущего индекса от индекса current+1 до индекса arr.length-1, чтобы найти максимальное значение rightMax.
Затем мы выбираем меньшее значение между leftMax и rightMax минус текущее значение. Если разница больше 0, мы можем добавить ее к общему количеству воды.
Код
var trap = function(height) {
//start from index one to index height.length-2
//first and last index cannot trap water
let totalWater = 0
for(let cur = 1; cur < height.length-1; cur++){
//check left side of current index, and find the max value
let leftMax = 0
for(let i = cur-1; i >= 0; i--){
leftMax = height[i]>leftMax ? height[i]:leftMax
}
//check right side of current index, and find the max value
let rightMax = 0
for(let i = cur+1; i < height.length; i++){
rightMax = height[i]>rightMax? height[i]:rightMax
}
//calculate water
let water = Math.min(leftMax, rightMax) - height[cur]
totalWater += water >0 ? water:0
}
return totalWater
};
Временная сложность: O(n²). Для каждого элемента массива мы итерируем левую и правую части.
Пространственная сложность: O(1).
Протестировать:
height [0,1,0,2,1,0,1,3,2,1,2,1] index 1 2 3 4 5 6 7 8 9 10 leftMax 0 1 1 2 2 2 2 3 3 3 rightMax 3 3 3 3 3 3 3 2 2 1 min bar 0 1 1 2 2 2 2 2 2 1 -valueOfInd 1 0 2 1 0 1 3 2 1 2 water 0 1 0 1 2 1 0 0 1 0 //if diff <0, water is 0 totalWater = 6
Динамическое программирование
Путем перебора мы выяснили, что нам нужно знать значения leftMax и rightMax для всех индексов. Мы можем использовать динамическое программирование и хранить их в массивах. Мы зададим два массива: leftMax и rightMax.
Во-первых, мы устанавливаем первому элементу в массиве leftMax первое значение в height для последующего сравнения. Затем мы можем перебрать height (слева направо), сравнивая height[i-1] и leftMax[i-1], чтобы найти значение leftMax для индекса i. Аналогично для массива rightMax, но начинаем с индекса height.length-1 (справа налево).
Давайте сначала посмотрим на некоторые тесты, которые помогут нам понять:
Протестировать
index 0 1 2 3 4 5 6 7 8 9 10 11
height [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
-->
leftMax [0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]
<--
rightMax [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1]
min bar 0 0 1 1 2 2 2 2 2 2 1 1
-valueOfInd 0 1 0 2 1 0 1 3 2 1 2 1
water 0 0 1 0 1 2 1 0 0 1 0 0//if diff<0, water is 0
totalWater = 6
Код
var trap = function(height) {
//use two arrays to track left and right max for each index
let leftMax = []
let rightMax = []
let totalWater = 0
//set first element of leftMax equals to first element in height for comparison later
leftMax[0] = height[0]
//same reason for the rightMax
rightMax[height.length-1] = height[height.length-1]
//fill the leftMax array
for(let i=1; i<height.length; i++ ){
leftMax[i] = leftMax[i-1]>height[i-1] ? leftMax[i-1] : height[i-1]
}
//fill the rightMax array
for(let i = height.length-2; i>=0; i--){
rightMax[i] = rightMax[i+1] > height[i+1]? rightMax[i+1] : height[i+1]
}
//find the min of leftMax and rightMax for each index, and calculate the water amount
for(let i = 0 ; i < height.length; i++){
let water = Math.min(leftMax[i],rightMax[i]) - height[i]
totalWater+= water > 0 ? water : 0
}
return totalWater
}
Временная сложность: O(n).
Пространственная сложность: O(n).
Два указателя
Из предыдущего анализа мы знаем, что нижняя полоса определяет, сколько воды может уловить индекс. Итак, у нас есть только два указателя. Один старт слева l, другой справа r. Нам также понадобятся две переменные для хранения максимального значения слева leftMax и справа rightMax. Когда leftMax меньше, чем rightMax , мы знаем, что можем использовать leftMax для определения воды, которая может быть захвачена с правой стороны индекса leftMax.
Логическая прогулка
while( l<=r ){
if leftMax < rightMax
if leftMax > height[l] calculate the water
else leftMax = height[l] //update leftMax
l++ //increment l
else //leftMax >= rightMax, rightMax is the lower bar
if rightMax > height[l] calculate the water
else rightMax = height[r] //update rightMax
r-- //decrease r
}
return total water
Код
var trap = function(height) {
let l = 0
let r = height.length - 1
let leftMax = height[l]
let rightMax = height[r]
let totalWater = 0
while(l<=r){
if(leftMax<rightMax){
if(leftMax > height[l]){
totalWater+= leftMax - height[l]
}else{
leftMax = height[l]
}
l++
}else{
if(rightMax > height[r]){
totalWater+= rightMax - height[r]
}else{
rightMax = height[r]
}
r--
}
}
return totalWater
};
Протестировать
index 0 1 2 3 4 5 6 7 8 9 10 11 height [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] l leftMax r rightMax leftMax<rightMax totalWater 0 0 11 1 true 0 1 0 11 1 true 0 2 1 11 1 false 0 2 1 10 1 false 0 2 1 9 2 true 1 3 1 9 2 true 1 4 2 9 2 false 2 4 2 8 2 false 2 4 2 7 2 false 2 4 2 6 3 true 3 5 2 6 3 true 5 6 2 6 3 true 6 7 2 6 3 true 6
Временная сложность: O(n).
Пространственная сложность: O(1).
