This is the 24th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Algorithm series, continue the day into a pawn ~ previous article portal:

  • Sliding Window
  • “Spicy Sky! Sliding Window of [sum Max] & [Maximum Set]”
  • Keep Moving! Sliding Window median and Sliding Rubik’s Cube
  • Ok, BFS, again!
  • Okay, DFS, Too!
  • From DFS to Backtracking: The N Queen Problem
  • Backtracking to Solve the Problem of [Telephone Number combination]

This paper will bring the two-pointer algorithm of the classic topic: rainwater problem;

Topic:

Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] output: 6 Example 2: input: height = [4,2,0,3,2,5] output: 9Copy the code

Answer:

Solution 1: Violent solution

For each element in the array, we find the highest position that water can reach after rain, which is equal to the lower value of the maximum height on both sides minus the current height.

If I is 2 and the maximum value on the left is index 1, it’s 1; The maximum on the right-hand side is 3, and how much water can be stored in this position is determined by the short side; For position I is 3, the maximum left hand side with the height of the current index position is 2.

The maximum on the right is still 3, and the minimum on the left and right is 2 and the height at the current index is 2 so ans is 0. Note The location whose index is 3 cannot store rainwater

JS implementation is as follows:

/** * @param {number[]} height * @return {number} */ var trap = function (height) { let res = 0; for (let i = 0; i < height.length; i++) { let max_letf = 0; let max_right = 0; For (let j = I; let j = I; j >= 0; j--) { max_letf = Math.max(max_letf, height[j]) } for (let j = i; j < height.length; j++) { max_right = Math.max(max_right, height[j]) } res += Math.min(max_letf, max_right) - height[i] } return res };Copy the code

Solution 2: Dual Pointers

When the maximum baffle on the left < the maximum baffle on the right and the left is quite close to the front, the final value plus the current maximum baffle on the left – the current value indicated by the left pointer (equivalent to the left as long as it does not exceed the right, the maximum baffle on the right is stable and the left has no brain near the sum) is greater than the reverse;

JS:

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let end = 0 
    let l = 0, r=height.length -1
    let maxl = 0,maxr=0
    while(l < r){
        maxl = Math.max(height[l],maxl)
        maxr = Math.max(height[r],maxr)
        if(maxl < maxr){
            end += maxl - height[l]
            l++
        }else{
            end += maxr - height[r]
            r--
        }
    }
    return end
};
Copy the code

Time complexity: O(n); Double pointer, YYDS!

Do you think double Pointers are similar to sliding Windows? More on dual Pointers to come

OK, the above is the share ~ writing is not easy, like encourage 👍👍👍

I am Anthony Nuggets, the public account of the same name, every day a pawn, dig a gold, goodbye ~