Title: Catch rain water

After solving the previous problem, the method of solving the problem was optimized and the new continent was discovered

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

In the previous solution of the problem was optimized, equivalent to doing a cache

Cache two

  • The maximum before each position from left to right
  • The maximum after every position from right to left

Caching is done so that you do not need to do redundant traversal every time, saving time.

The equivalent of

Height =,1,0,2,1,0,1,3,2,1,2,1 [0] / / from left to right through the left =,1,1,2,2,2,2,3,3,3,3,3 [0] / / traverse right = from right to left ,3,3,3,3,3,3,3,2,2,2,1 [3]Copy the code

According to the height of the left and right take the smallest between them, and then subtract their own column height is the water storage.

Pseudo code

rain = min(left[i], right[i]) - height[i]
Copy the code

Time complexity: O(n)

Space complexity: O(n)

AC code

function trap(height = []) {
  const len = height.length

  // Walk through the initialization array from left to right and initialize the first position
  let left = new Array(len)
  left[0] = height[0]
  // Walk through the initialization array from right to left and initialize the end position
  let right = new Array(len)
  right[len - 1] = height[len - 1]
  
  / / the result
  let res = 0

  for (let i = 1; i < len; i++) {
    left[i] = Math.max(height[i], left[i - 1])}for (let i = len - 2; i >= 0; i--) {
    right[i] = Math.max(height[i], right[i + 1])}for (let i = 0; i < len; i++) {
    res += Math.min(left[i], right[i]) - height[i]
  }

  return res
}
Copy the code

conclusion

Although the cache time has been optimized, the space has become O(N). Compared with the previous violent method, it is equivalent to exchanging space for time. The balance between the two is the best choice.

To be honest, I do not understand why this method is dynamic programming, so I will come back to make up for it.