Today I found a very interesting algorithm question. The following is its algorithm description, which comes from an interview question on Twitter.
twitter puddles algorithm description
Look at a picture first
The numbers in the figure above are described according to the content of an array. Finally, the height of a wall will be simulated according to the size of each number, and a wall will be generated. Ask you, when it rains, how much water can this wall be filled with, in 1 as the counting unit.
Here is a wall after filling the water
After reading the above picture, do you feel it is fun? Indeed, let’s briefly analyze its algorithm implementation below.
In fact, this principle is relatively simple, there are a few key points:
1. There is definitely no water on the left and right sides
2. The height of the water load depends on the minimum value of the two maximum values on the left and right sides of the oneself
Let's use js to implement it simply:
The code copy is as follows:
/**
* Calculate how much water can be installed on the wall with array terms as the height
* Array example[2,5,1,2,3,4,7,7,6,9]
**/
function getWaterCounts(arg){
var i = 0,
j = 0,
count = 0;
// Both the first and last items must be excluded
for(i = 1; i < arg.length - 1; i++){
var left = Math.max.apply(null, arg.slice(0, i + 1));
var right = Math.max.apply(null, arg.slice(i, arg.length));
var min = left >= right ? right : left;
// The maximum value of the left and right sides shall prevail
// If the current value is greater than or equal to this value, do nothing
if(arg[i] < min){
count += min - arg[i];
}
}
console.log(count);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11
Summarize
Hehe, isn't the implementation quite simple? In fact, as long as you are willing to think, you can use js to implement many fun things.