Title: Catch rain water

See force buckle for details

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

First of all, clear

  • Rainwater can only be stored between two pillars
  • They can’t store rainwater at the end
  • Stormwater storage is calculated with short columns (short board theory)

Then you can calculate how much rain is stored in each location, not including the end

Such as:

  • The position with index 1 cannot be stored because the maximum height of the previous column was 0
  • For the position with index 2, the height of the highest column on the left is 1, and the height of the highest column on the right is 3. The short board theory takes the shortest column as1, minus the current height of itself0, it is1-0, the current location can be stored1One unit of rain.
  • By calculation in turn, it can be concluded that only the highest column on the left and the highest column on the right of the current position can be found each time, and the lower column of the two can be subtracted from the height of the column in the current position, which is the amount of rainwater stored.

Produces the following pseudocode (to get the amount of rain at the current location)

rain = min(leftMaxHeight, rightMaxHeight) - selfHeight
Copy the code
  • rainThe rain water
  • leftMaxHeightThe highest column height on the left,rightMaxHeightHighest column height on the right
  • selfHeightColumn height of current position

AC code

The following code is for brute force resolution, and there is obviously room for optimization.

function trap(height = []) {
  if (height.length === 0) {
    return 0
  }

  const n = height.length
  / / the result
  let res = 0

  for (let i = 1; i < n - 1; i++) {
    let l_max = 0 // The highest column height on the left
    let r_max = 0 // The highest column height on the right

    for (let j = i; j < n; j++) {
      // Find the highest column on the right
      r_max = Math.max(r_max, height[j])
    }

    for (let j = i; j >= 0; j--) {
      // Find the highest column on the left
      l_max = Math.max(l_max, height[j])
    }

    res += Math.min(l_max, r_max) - height[i]
  }

  return res
}
Copy the code

conclusion

Time complexity O(N^2)

Space complexity O (1)

In fact, you can use double Pointers to solve the problem, which will optimize a lot.