Author: Hanpeng_Chen

Public account: front-end geek technology

Today we will do a problem on LeetCode, the original problem link: 42. Catch rain water

Topic describes

Given n non-negative integers representing the height diagram of each column of width 1, calculate how much rain can be received by the columns arranged in this order after it rains.

Example 1:

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

Output: 6

Explanation: above is the height map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water can be connected (the blue part represents rain water).

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Thought analysis

Violence to solve

Train of thought

According to the picture of Example 1, we can understand the title clearly: the width of each column is 1, so we only need to calculate the volume of rainwater on each column, and then sum it up to get the total volume of rainwater.

For the amount of water stored on each column, according to the principle of barrels, we simply find the highest position where water can reach after rain, i.e. the smaller value of the maximum height on both sides minus the value of the current height.

Solution steps:

  • Initialize sum = 0
  • Walk through the groups from left to right:
    • Initialize the maximum height of both sides to 0: left_max = 0, right_max = 0
    • Iterates to the left from the current element and updates:
      • left_max = Math.max(left_max, height[k])
    • Iterates from the current element to the right and updates:
      • right_max = Math.max(right_max, height[k])
    • Add math.min (left_max, right_max) -height [I] to sum

Implementation code:

var trap = function(height) {
    let len = height.length;
    let sum = 0;
    for (let i = 1; i < len - 1; i++) {
        let left_max = 0, right_max = 0;
        for (let k = i; k >= 0; k--) {
            left_max = Math.max(left_max, height[k])
        }
        for (let k = i; k < len; k++) {
            right_max = Math.max(right_max, height[k])
        }
        sum += (Math.min(left_max, right_max) - height[i])
    }
    return sum
};
Copy the code

Complexity analysis

The method uses double traversal, so the time complexity is O(n^2); The space complexity is O(1)

Brute force solution optimization

In the violent solution above, each time in order to find the left and right maxima of position I, it has to walk left and right once, so there is a double walk. If we find out the left and right maximum values of each position in advance and store them, and then directly go to the corresponding values when traversing the number group later, there will be no double traversal, and the time complexity is reduced to: O(n).

steps

  • Find the highest column height from the leftmost end of I in the array left_max;
  • Find the height of the highest column from I to the rightmost end of the array right_max;
  • Traversing the number group:
    • Math.min(left_max[I], right_max[I]) -height [I]

The implementation code

var trap = function(height) {
    if(! height || height.length ===0) return 0;
    let sum = 0;
    let left_max = [];
    let right_max = [];
    let len = height.length;
    left_max[0] = height[0];
    for (let i = 1; i < len; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1])
    }
    right_max[len - 1] = height[len - 1];
    for (let i = len - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1])}for (let i = 1; i < len - 1; i++) {
        sum += Math.min(left_max[i], right_max[i]) - height[i];
    }
    return sum;
};
Copy the code

Complexity analysis

  • Time complexity: the total time complexity is O(n), so the total time complexity is O(n)
  • Space complexity: extra O(n) space is used to store the left_max and right_max arrays, so the space complexity is O(n).

The solution is to reduce the running time by swapping space for time.

Double pointer

Let me introduce another good solution: the double pointer solution.

The core of the violent solution is to find the maximum value of the left and right sides, but we will find through careful analysis that as long as right_max[I] > left_max[I], the maximum water storage of column I is determined by left_max; If left_max[I] > right_max[I], the value is determined by right_max.

With this idea in mind, we scan the array from left to right first. We can assume that if there are higher columns on one side (for example on the right), the height of the water depends on the height in the current direction (from left to right). When we find that the bar on the other side (right) is not the highest, we start to walk in the opposite direction (right to left).

At this point we maintain the left and right Pointers, through the two Pointers alternately traversal, to achieve a traversal completed.

For the position left, the maximum value on the left must be left_max and the maximum value on the right must be greater than or equal to right_max. If left_max < right_max, then it will be able to calculate how much water it can hold, regardless of whether there will be a larger value on the right, so when height[left] < height[right], we will deal with the left pointer. Instead, we deal with the right pointer.

Steps:

  • Initialize the left pointer to 0 and the right pointer to height.length-1;
  • While left < right:
    • if height[left] < right[right]:
      • left_max = Math.max(left_max, height[left])
      • Sum left_max-height [left] to sum
      • left++
    • else
      • right_max = Math.max(right_max, height[right])
      • sum += right_max – height[right]
      • right–

The implementation code

var trap = function(height) {
    let sum = 0;
    let left_max = 0;
    let right_max = 0;
    let left = 0;
    let right = height.length - 1;
    while(left < right) {
        if (height[left] < height[right]) {
            left_max = Math.max(left_max, height[left]);
            sum += left_max - height[left];
            left++;
        } else {
            right_max = Math.max(right_max, height[right]); sum += right_max - height[right]; right--; }}return sum;
};
Copy the code

Complexity analysis

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

If you find this helpful:

1. Like it so more people can see it

2, pay attention to the public number: FrontGeek technology, we learn and progress together.

This article is participating in the “Nuggets 2021 Spring Recruiting activity”, click to see the details of the activity