directory

When I looked at the interview questions before, I saw a problem of receiving rain water. After discussing it with yellow duck, I felt it was very interesting. Here I share this solution with you. Later, I saw this problem in LeetCode with the number 42. If you are interested, you can do it.

Problem description

Given n non-negative integers representing the height diagram of each column of width 1, calculate how much rain can be caught by the columns aligned with each other after rain.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1

Example 2:

Height = [4,2,0,3,2,5

Can you think about what you would do if you faced this kind of problem?

Problem analysis

First we can draw the length of the column based on the array given.

So how do we determine how much rain we’re getting? Of course, both of them are high and the middle is low to store the water, and the shaded area below is where the water is stored.

So we need to do a count of the left and right highest water levels, using two auxiliary arrays

One is used to store the maximum amount of rain on the left and one is used to store the maximum amount of rain on the right.

Choose the smallest of the two as the amount of water to store

Subtract the height of your column, of course. The rest is just rain to catch.

The code

function trap(height) {
    if(! height.length)return 0;
    let left = []
    let right = []
    let lmax = rmax = 0
    let len = height.length
    let result = 0
    // Find the maximum amount of water
    for(let i = 0; i < len; i++) {
        lmax = Math.max(height[i], lmax)
        rmax = Math.max(height[len-i-1], rmax)
        left[i] = lmax
        right[len- i - 1] = rmax
    }
    // Calculate the smallest and add up
    for(let i = 0; i < len; i++) {
        result += Math.min(left[i],right[i]) - height[i]
    }
    return result
};
Copy the code

If you want to optimize your writing, you can use reduce on the second pass

function trap(height) {
    if(! height.length)return 0;
    let left = []
    let right = []
    let lmax = rmax = 0
    let len = height.length
    for(let i = 0; i < len; i++) {
        lmax = Math.max(height[i], lmax)
        rmax = Math.max(height[len-i-1], rmax)
        left[i] = lmax
        right[len- i - 1] = rmax
    }
    return height.reduce((prev, item, index) = > {
        return prev + Math.min(left[index],right[index]) - item
    }, 0)};Copy the code

Analysis of the

• Time complexity O(n)
• Space complexity O(n)

In fact, the storage of the values of the right array can be omitted, although both are O(n) space complexity, but also a small optimization point.

function trap(height) {
    if(! height.length)return 0;
    let left = []
    let lmax = rmax = 0
    let len = height.length
    let result = 0
    for(let i = 0; i < len; i++) {
        lmax = Math.max(height[i], lmax)
        left[i] = lmax
    }
    // traverse from back to front
    for(let i = len - 1; i >= 0; i--) {
        rmax = Math.max(height[i], rmax)
        result += Math.min(left[i],rmax) - height[i]
    }
    return result
};
Copy the code