Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

Read pre-benefit computer classics

This year, Beijing has been especially rainy. The whole two days before the Mid-Autumn Festival, are spent in the rain, not the past Mid-Autumn Festival fast atmosphere, fortunately, in the Mid-Autumn Festival that day, the weather is clear, can be regarded as the whole holiday draw on a satisfactory end.

Listening to the rhythm of the falling rain, remember some time ago in the pulse to see a post, Ali P8 to interview a certain, hanging on the algorithm. And I interviewed a company three years ago, also fell on the same algorithm. Is the so-called fall into the pit and gain wisdom, the algorithm reorganized the next, share with you, I hope to be useful.

After the rain

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

Explanation: the height diagram above is represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], in which case 6 units of rain can be caught (blue is rain)

At first glance, I felt very simple, but I didn’t know where to start. We will follow a step-by-step approach to the solution of this problem.

Violent solution

The moment you see the question, out of the mindset, you must look for the lowest part of the “concave” groove, and then… And so on, more and more head big, until give up.

Let’s think about how much rain we can put on each pillar. So how high does each column hold the rain water? It is the difference between the maximum height of the left and right sides of the column and its height. It is more laborious to understand in words, and it is more convenient for everyone to understand in the way of diagrams.

Next, we will calculate the column coordinates (3)-(7), namely the water volume inside the red box.

We first define four variables:

  • Res is the total amount of water, initialized to 0
  • Height Height of the current column
  • Left_max Maximum height to the left (including the current column itself)
  • Right_max Maximum height to the right (including itself)

First, calculate the amount of water at pillar (3). The maximum height left_max is 2, and the maximum height right_max is 3, so the amount of water in horizontal coordinate 3 is min(left_max, right_max) -height is not min(2, 3) -2. That is to say, pillar (3) can hold 0.

Then we calculate the amount of water at pillar (4). According to the above calculation rules, if the maximum height on the left is 2 and the maximum height on the right is 3, then the water volume of column (4) can be min(2, 3) -1, and the answer is 1.

Then calculate the water capacity of column (5). According to the above calculation rules, the maximum height on the left is 2, and the maximum height on the right is 3, so the water capacity of column (5) is min(2, 3) -0, and the answer is 2.

Then calculate the water capacity of column (6). According to the above calculation rules, the maximum height on the left is 2, and the maximum height on the right is 3, so the water capacity of column (6) is min(2, 3) -1, and the answer is 1.

Finally, calculate the water capacity of column (7), the maximum height on the left is 3, and the maximum height on the right is 3, so the water capacity of column (7) is min(3, 3) -3, i.e. 0.

Therefore, the amount of water between pillar (3) and pillar (7) is res = 0 + 1 + 2 + 1 + 0 = 4.

Code implementation one:

int trap(vector<int>& height) { int res = 0; for (int cur = 0; cur < height.size(); ++cur) { int left_max = 0; int right_max = 0; For (int left = 0; left <= cur; ++left) { left_max = std::max(left_max, height[left]); } for (int right = cur; right < height.size(); ++right) { right_max = std::max(right_max, height[right]); } res += STD ::min(left_max, right_max) -height [cur]; } return res; }Copy the code

There is a trick in the above rules, that is, when calculating the highest on both sides, the height of the column itself is taken into account, so as to facilitate calculation when calculating the amount of water.

Assuming the calculation of column (3), if the maximum height of the column (3) on both sides is not included in the calculation of the maximum height of the column (3) itself, then the maximum height on the left side of the column (3) is 1, the maximum height on the right is 3, when calculating the amount of water, we need to judge min(lext_max, right_max) and the size of the column (3) itself, Otherwise negative values will appear, and the code implementation is as follows.

Code Implementation two

int trap(vector<int>& height) { int res = 0; for (int cur = 0; cur < height.size(); ++cur) { int left_max = 0; int right_max = 0; For (int left = 0; int left = 0; left < cur; ++left) { left_max = std::max(left_max, height[left]); } for (int right = cur + 1; right < height.size(); ++right) { right_max = std::max(right_max, height[right]); } int mx = STD ::min(left_max, right_max); If (mx > height[cur]) {res += mx-height [cur]; } } return res; }Copy the code

The brute force method, which is simple to understand, has a time complexity of O(n2). After submission, there is no doubt that it will TLE. Now we optimize the brute force method in other ways.

For ease of understanding, later implementations will use the idea of implementation two.

Dynamic programming

After seeing the implementation of the violence method, we already have the basic idea. Its time complexity is O(n2), and the time is mainly spent on finding the maximum column height on both sides. So is there a way to get the heights of all the columns by going through them a couple of times?

We still have

Height =,1,0,2,1,0,1,3,2,1,2,1 [0]

As an example, calculate the bilateral maximum value.

Left maximum

Define an array left_max, where left_max[I] is the maximum height left of the i-th column of code.

Now let’s calculate the maximum height on the left side of the column:

  • Column (0), maximum height on the left side is 0(there is no column on the left side)
  • Pillar (1), maximum height 0 on the left side (only pillar 0 on the left)
  • Column (2), left maximum height of 1(maximum of array [0 1])
  • Column (3), left maximum height is 1
  • Column (4), left maximum height of 2
  • Column (5), left maximum height is 2(array maximum)
  • Column (6), maximum height on the left is 2
  • [0 1 0 2 1 0 1] column (7), left maximum height of 2
  • [0 1 0 2 1 0 1 3] column (8), the left maximum height is 3
  • [0 1 0 2 1 0 1 3 2]
  • [0 10 2 10 1 3 2 1]
  • Column (11), the maximum height on the left is 3([0 1 0 2 1 0 1 3 2 1 2]

From the analysis of the above rules, we find that there is a certain rule to follow, that is, the maximum height of the left side of the current column is Max (the maximum height of the left side of the previous column, the height of the previous column).

The code is shown as follows:

std::vector<int> left_max(height.size(), 0);
for (int i = 1; i < height.size(); ++i) {
  left_max[i] = std::max(left_max[i - 1], height[i]);
}
Copy the code

With a few changes to the above code, it looks like this:

std::vector<int> left_max(height.size(), 0);
int mx = 0;
for (int i = 0; i < height.size(); ++i) {
  left_max[i] = mx;
  mx = std::max(mx, height[i]);
}
Copy the code
Right maximum

Define array right_max where left_max[I] is the maximum height to the right of the ith column of code.

To calculate the right-hand maximum, you must start from the last one and move forward (if you start from the first one, it is the same as the brute force method). Height =,1,0,2,1,0,1,3,2,1,2,1 [0]

  • Column (11), maximum height on the right side is 0(there is no column on the right side)
  • Column (10), the maximum height on the right side is 1(maximum of [1])
  • Column (9), the maximum height on the right side is 2(maximum of [2 1])
  • Column (8), the maximum height on the right side is 2(maximum of [1 2 1])
  • Column (7), the maximum height on the right side is 2(maximum of [2 1 2 1])
  • Column (6), the maximum height on the right side is 3(maximum of [3 2 1 2 1])
  • Column (5), the maximum height on the right side is 3(maximum of [1 3 2 1 2 1])
  • Column (4), the maximum height on the right side is 3(the maximum of [0 1 3 2 1 2 1])
  • Column (3), the maximum height on the right side is 3(the maximum of [1 0 1 3 2 1 2 1])
  • Column (2), the maximum height on the right side is 3(the maximum of [2 1 0 1 3 2 1 2 1])
  • Column (1), the maximum height on the right side is 3(the maximum of [0 2 1 0 1 3 2 1 2 1])
  • Column (0), the maximum height on the right side is 3(the maximum of [1 0 2 1 0 1 3 2 1 2 1])

Now that we have calculated the bilateral maximum, let’s implement the following code:

int trap(vector<int>& height) { int res = 0; std::vector<int> left_max(height.size()); std::vector<int> right_max(height.size()); int mx = 0; For (int I = 0; i < height.size(); ++i) { left_max[i] = mx; mx = std::max(mx, height[i]); } mx = 0; For (int I = height.size() -1; i >= 0; --i) { right_max[i] = mx; mx = std::max(mx, height[i]); } for (int I = 0; i < height.size(); ++i) { int mn = std::min(left_max[i], right_max[i]); if (mn > height[i]) { res += mn - height[i]; } } return res; }Copy the code

Compared with the violent method, the time complexity of the above code is optimized to O(n) and AE after submission.

There are three loops in the above code, with a spatial complexity of O(2n), some of which are used as c++ coder, which is intolerable. Can we optimize them again? We see that cycle 3 is simply calculating rainfall. Can we combine cycle 2 and cycle 3 and optimize the spatial complexity? It must be. In order to read it easily, we implement the code as follows:

int trap(vector<int>& height) { int res = 0; std::vector<int> v(height.size()); int mx = 0; For (int I = 0; i < height.size(); ++i) { v[i] = mx; mx = std::max(mx, height[i]); } mx = 0; For (int I = height.size() -1; i >= 0; --i) { int mn = std::min(mx, v[i]); mx = std::max(mx, height[i]); if (mn > height[i]) { res += mn - height[i]; } } return res; }Copy the code

Double pointer

Dynamic programming method, time complexity and space complexity are O(n), next we introduce an algorithm with only one cycle and space complexity of O(1), this is the double pointer algorithm.

The core idea of the rain water receiving algorithm is to calculate the current column water volume, that is, the difference between the smaller of the maximum value on the left and right sides and the current column. We first find the smaller value of the two columns of the array, and then compare the two columns to the smaller value. If the smaller value is the left column, the left column moves to the right until it is greater than the current smaller value. Conversely, if the smaller value is the right column, the right column moves to the left until it is greater than the current value.

The left and right Pointers point to the beginning and end of the array respectively and scan from both sides to the middle. Within the range determined by the current two Pointers, compare the two ends first to find the smaller value. If the smaller value is the value pointed to by left, scan from left to right; if the smaller value is the value pointed to by right, scan from right to left. If the value encountered is smaller than the smaller value, the difference value is saved into the result. If the value encountered is large, the new window range is determined, and so on until the left and right Pointers overlap

int trap(vector<int>& height) {
  int res = 0;
  int left = 0;
  int right = height.size() - 1;
  while (left < right) {
    int mn = min(height[left], height[right]);
    if (mn == height[left]) {
      ++left;
      while (left < right && height[left] < mn) {
        res += mn - height[left++];
      }
    } else {
      --right;
      while (left < right && height[right] < mn) {
        res += mn - height[right--];
      }
    }
  }
  return res;
}
Copy the code

Monotonous stack

This method is compared with the previous two methods (violent method and double-pointer method). If the former two methods are to calculate the total amount of water on each column (i.e. by column), then the monotone stack method is to calculate the amount of water on each layer by row, as shown below:

Every row of water is bound to get stuck on the pole. So if you traverse the column from left to right, if you’re falling in height, you’re obviously not holding water. If the height goes up, it means there’s a low point in the middle, and there’s water in between. And the height of the drop is maintained by a monotonic stack, where we just put the subscript.

If the stack is empty or the current height is less than or equal to the top height of the stack, then the coordinate of the current height is pushed onto the stack. Note that the coordinate is pushed onto the stack instead of the height directly, so that the horizontal distance can be calculated later. When it is larger than the top of the stack, it means that there may be a pit, which can hold rain water. At this time in at least one stack height, if there is only one, so can’t form a pit, skip, if a surplus, so the elements in the stack out as a pit, a new stack element is left boundary, the height is right, as long as the two smaller, minus the height of the pit, the length is right boundary coordinates minus the left boundary coordinates will be a reduction of 1, When you multiply the two, you get the amount of water.

Again, we use the array height = [0,1,0,2,1,0,1,3,2,1,2,1,1] to illustrate the use of monotonic stacks.

Assuming the initial value of RES is 0, it is used to calculate the maximum water capacity of the column height represented by the height array.

  • At initialization, the stack is empty.

  • Since the stack is empty, subscript 0 is pushed onto the stack, as shown below:

  • Since the array height[1] = 1 is larger than the number at the top of the stack, subscript 0 goes out of the stack and subscript 1 goes on the stack.

  • Since subscript 2 points to a value less than the top of the stack, subscript 2 is pushed onto the stack.

  • At this point, the subscript points to 3. Since the value pointed to by subscript 3 is larger than the value pointed by the subscript at the top of the stack, then the stack is out and the water volume of the wheel is calculated ((min(2, 1) -0) * (3-1-1) = 1), that is, the increment is 1. At this time, RES = 1.

  • Since the height of subscript 1 is less than the height of subscript 3, subscript 1 is pushed out of the stack, and when the stack is empty, subscript 3 is pushed forward.

  • Subscript 4 points to a value less than the value at the top of the stack (1 < 2), and subscript 4 is pushed

  • Subscript 5 points to a value less than the value at the top of the stack (0 < 1), and subscript 5 is pushed

  • At this point, the value indicated by subscript 6 is 1, which is greater than the value indicated by subscript 6 at the top of the stack (1 > 0), then the stack is removed, and the increment of water is calculated at the same time (min(1, 1) -0) * (6-4-1)), and the increment is 1. At this point, res = 1 + 1 = 2.

  • The value pointed to by subscript 6 is equal to the value pointed to at the top of the stack (1 = 1), and subscript 6 is pushed

  • At this point, the subscript points to 7, and its value is greater than the top value of the stack (3 > 1), then the stack is pushed out of the stack, the calculated increment is (min(3, 1) -1) * (7-4-1)), and the increment is 0, then res = 1 + 1 + 0 = 2

  • At this point, the subscript is still 7 and the top value of the stack is 4. Since the current subscript pointing value is greater than the top pointing value of the stack, then the stack is out and the increment of water is calculated ((min(3, 2) -1) * (7-3-1)) with the increment of 3. At this time, res = 1 + 1 + 0 + 3 = 5

Calculate incremental water capacity

  • In this case, there is only subscript 3 in the stack, and the value it points to is smaller than the current value (2 < 3), then the stack is removed

  • If the stack is empty, the subscript 7 is pushed

  • Subscript 8 is less than the top of the stack (2 < 3), subscript 8 is pushed

  • The subscript 9 value is less than the top value of the stack (1 < 2), and the subscript 9 is pushed

  • At this point, the subscript is 10, and its corresponding value is greater than the top pointing value (2 > 1), then the stack is pushed out of the stack, and the increment is calculated (min(2, 2) -1) * (10-8-1)), and the increment is 1. At this point, res = 1 + 1 + 0 + 3 + 1 = 6

  • Subscript 10 indicates that the value is less than the top value of the stack

  • Subscript 11 indicates a value less than the top value of the stack

At this point, the array loop ends, and even though there are still numbers in the stack, coordinates 7, 8, 10, 11, pointing to values 3, 2, 2, 1, they no longer form a groove to hold water, so the algorithm ends.

The code implementation is as follows:

int trap(vector<int>& height) {
  stack<int> st;
  int i = 0, res = 0, n = height.size();
  while (i < n) {
    if (st.empty() || height[i] <= height[st.top()]) {
    st.push(i++);
} else {
    int t = st.top(); st.pop();
    if (st.empty()) continue;
    res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - 1);
    }
  }
  return res;
}
Copy the code

Write in the last

Framework or underlying principle analysis, need to research a lot of information, research and analysis of the source code, very energy. So in later articles, there may be algorithms (Leetcode classic algorithm), interviews (for some of the classic questions encountered in interviews), and architecture and low-level intersperses.