JavaScript implementation of twitter puddles algorithm example_javascript skills

I found a very interesting algorithm question today. The following is its algorithm description, which is derived from an interview question on Twitter.

Twitter puddles algorithm description

Look at a picture first

The numbers in the picture above are described based on the contents of an array. Finally, the height of a wall will be simulated based on the size of each number, and finally a wall will be generated. I ask you, when it rains, this wall can be installed How much water, in units of 1.

Here is what a wall looks like after filling it with water

After reading the above picture, I think it is very interesting. Indeed, let’s briefly analyze its algorithm implementation

In fact, this principle is relatively simple. There are a few key points in total:

1. The far left and rightmost sides must not be filled with water
2. The height of water filling depends on the minimum of the two maximum values ​​on the left and right sides

Below we use js to simply implement it:

Copy code The code is as follows:

/**
* Calculate how much water a wall with the array item as the height can hold
* 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 smaller of the maximum values ​​on 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

Summary

Hey, the implementation is quite simple, in fact, as long as you are willing to think, you can achieve a lot of fun things with js.