LeetCode——42. Connected to rainwater (double pointer)

Title Description

Their thinking

Receiving rainwater is a typical double pointer problem , First define a left pointer and a right pointer .

1. initialization

   • The left pointer points to the first element
   • The right pointer points to the last element

2. Define a final return of and sum=0.

3. Define two variables to store the maximum value on the left and the maximum value on the right .

4. The loop condition is that the left pointer is smaller than the right pointer .

5. Each time the loop is entered, the maximum values of the tracks pointed by the left and right pointers are updated .

6. If the maximum value of the left pointer is less than the maximum value of the right pointer , The rainwater that can be received is the maximum value of the left pointer minus the height of the current position , Then the left pointer moves to the right .

7. If the maximum value of the left pointer is greater than or equal to the maximum value of the right pointer , Calculate the maximum value of the right pointer minus the current right pointer height , Then move the right pointer to the left .

In order to make it easier for everyone to understand this topic , We can do the same as the following picture , Draw the changes of the left and right pointers and the maximum value in turn , Last return maximum .

AC Code

var trap = function(height) {
    
  let [left, right] = [0, height.length - 1];
  let [leftMax, rightMax] = [0, 0];
  let sum = 0;

  while (left < right) {
    
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);

    if (leftMax < rightMax) {
    
      sum += leftMax - height[left++];
    } else {
    
      sum += rightMax - height[right--];
    }
  }
  return sum;
};

reflection

Receiving rain is a topic that is often ridiculed on the pulse , Of course, this question often appears in interview questions such as Niuke , So we must understand this problem , The double pointer question is a kind of question that is often taken in an interview , The most important thing to solve this kind of problem is to figure out when the left pointer and the right pointer move , What is the meaning of the maximum value of the left pointer and the maximum value of the right pointer .