Previous solutions

Violence to solve

Dynamic programming solution

Title: Catch rain water

See force button for details of the original question

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: 6Copy the code

Thought analysis

After solving the previous two problems, I found that there were always multiple iterations, just as there was no way to solve the problem once. It is obvious that dual Pointers can be optimized.

The idea behind the previous dynamic programming was to cache the highest column before each position from left to right, and the highest column after each position from right to left. Now with dual Pointers it is possible to compute both values while running, so that the result can be computed in one walk.

First, define the two variables as the maximum value before the current column leftMax and the height of the highest column after the current position leftMax, and the initial value as the corresponding 0 and the value of the last position in the array. We also need two Pointers to indicate the current position of the left and right Pointers left and right, and the left and right indexes also default to 1 and and the boundary of this loop is the index where the left pointer is less than the right pointer.

If the left pointer value is less than the right pointer value, then compare it with the height of the highest column before the current position (leftMax). If it is greater than leftMax, the height of the column at the current position is assigned to leftMax; if it is less than or equal to leftMax, it means that water can be stored, then the water storage can be calculated. Res = min(leftMax, rightMax) -height [I]

If the left pointer is greater than or equal to the right pointer, the operation is similar.

Only one loop is carried out, and no redundant variables are used, so: time complexity: O(n) Space complexity: O(1)

AC code

/ / double pointer
function trap(height = []) {
  let len = height.length

  let leftMax = 0
  let rightMax = 0

  let left = 0
  let right = len - 1

  let res = 0

  while (left < right) {
    if (height[left] < height[right]) {
      if (leftMax < height[left]) {
        leftMax = height[left]
      } else {
        res += leftMax - height[left]
      }
      left++
    } else {
      if (rightMax < height[right]) {
        rightMax = height[right]
      } else {
        res += rightMax - height[right]
      }
      right--
    }
  }

  return res
}

/ / test
console.log(trap([0.1.0.2.1.0.1.3.2.1.2.1]))
Copy the code

conclusion

On the previous dynamic programming optimization again, this time the code is relatively good, time and space, should meet the requirements. Double pointer before understanding, but encounter related questions, or can not immediately think of, or have to brush more questions. (Enough for three articles on one topic.)