This is the fifth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

This series has no flower head, is pure LeetCode problem breakdown analysis, not with a line or a small group of clever solution, but with clear code and simple enough ideas to help you clarify the meaning of the problem. Let you in the interview no longer afraid of algorithms written tests.

148. Trapping of rainwater

The label

  • Double pointer
  • difficult

The title

Leetcode portal

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

Type: height = [0.1.0.2.1.0.1.3.2.1.2.1] output:6Explanation: The above is made up of the array [0.1.0.2.1.0.1.3.2.1.2.1], in which case, can be connected6Units of rain (the blue part is rain).Copy the code

Example 2

Type: height = [4.2.0.3.2.5] output:9
Copy the code

The basic idea

We get a problem, if you can’t think of another good method, don’t leng, can solve the problem, inefficient code is also ok, first solve it! Most of any topic has a violent way, simple thinking, but not high efficiency.

Let’s start with the exhaustive method, which simply means traversing how much water can be put in each position, as shown here

L_maxH = 3, r_maxH = 4, the highest left wall l_maxH = 3, the highest right wall r_maxH = 4, the principle of cask take the smaller one, and then subtract the height of the current column I to get the volume of water, is 3-1 = 2

The code is also very violent

var trap = function(height) {
  let res = 0, len = height.length
  if (len === 0) return 0

  // * * * * * * * * * *
  for (let i = 1; i < len-1; i++) {
    let l_maxH = 0
    let r_maxH = 0

    // Look for the highest pillar on the right
    for (let j = i; j < len; j++) {
      // Update the maximum value for each round of comparison, and end up with the highest column on the right at that position
      r_maxH = Math.max(r_maxH, height[j])
    }

    // Similarly, look for the highest column on the left
    for (let k = i; k >= 0; k--) {
      // Update the maximum value for each round of comparison, and end up with the highest column on the right at that position
      l_maxH = Math.max(l_maxH, height[k])
    }

    // Compare the minimum values of the columns on both sides.
    // Then minus the current height is the amount of water that can be stored at that position
    res += Math.min(l_maxH, r_maxH) - height[i]
  }

  return res
}

let height = [0.1.0.2.1.0.1.3.2.1.2.1]
console.log(trap(height))
Copy the code

O(n^2) so what are some ways to optimize it

Double pointer

In fact, the overall idea is roughly similar. There are two Pointers approaching from both ends to the middle, as shown in the figure. In fact, the water capacity of the coordinate position of the left pointer is only related to l_maxH, and has nothing to do with r_maxH. So as long as the dynamic update left and right the highest wall or take the bucket short board to do the wall, calculate the capacity of each position can be.

Double pointer

var trap = function(height) {
  let len = height.length, res = 0
  if (len === 0) return 0
  Left -> right -> left -> right -> left -> right
  let left = 0
  let right = len - 1
  // The maximum value on the left is obtained by traversing from left to right
  let l_max = height[0]
  // The maximum value on the right is obtained by traversing from right to left
  let r_max = height[len-1]
  while (left <= right) {
    l_max = Math.max(l_max, height[left])
    r_max = Math.max(r_max, height[right])
    // Take the short wall
    if (l_max <= r_max) {
      res += l_max - height[left]
      left++
    } else {
      res += r_max - height[right]
      right--
    }
  }
  return res
};
Copy the code

In addition, I would like to recommend this series of articles, very deep in simple, for the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

That’s all for today, if you want to brush the questions with me, you can add my wechat oh, click here to make a friend Or search my wechat id, infinity_9368, you can chat and add my password “Tianwang Gai Tihu” in English. Please send me the verification message presious Tower Shock the Rever Monster, I read it and I will pass it, I will do my best to help you after I add it, but pay attention to the way you ask, I suggest you read this article first: The Wisdom of Asking questions

reference