This is the 11th day of my participation in the August Wenwen Challenge.More challenges in August

Hello, everyone. Today, I’m going to share with you the next LeetCode difficult problem: rain

The title

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. (Image reproduced by leetCode)

Example 1: input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] 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 six units of rain can be caught (the blue parts are rain).Copy the code
Height = [4,2,0,3,2,5Copy the code

Analysis of the

1. The width of the column is 1. The height of the column is an integer and may have duplicate values

2. Observe that the area of rain water is equal to the width between the two pillars * (minimum of the two pillars – height of the depression)

3. Return the total area of rainwater

solution

1.stack

2. The method of violence

Solution a:stack

Train of thought1.Stack maintains a monotonically decreasing stack, iterating over height, and calculating the area when height[I] is larger than the top of the stack, as follows1.Stack top out of stack, as the bottom height of the depression top2.The remaining top of the stack serves as the boundary of the depression3.Height [I] is the right border4.The height of the pool is zeroMath.min(left,right)-top1.Since there may be duplicate values, when the height of left is the same as the height of top, the height is calculated to be zero0And the area is zero. The pool has height only when the height of left is greater than that of top5.The width of the pool is i-left index -1
  6.We have to add up because we need the total area2.Returns the total area */var trap = function (height) {
  // stack stores index
  const stack = [];
  let area = 0;
  // The left edge of the storage pool
  const left = [];
  // The right edge of the storage pool
  const right = [];
  // The bottom height of the storage pool
  const bottom = [];
  for (let i = 0; i < height.length; i++) {
    // If the top element of the stack is smaller than the new element, the right edge of the pool is encountered
    while (stack.length && height[stack[stack.length - 1]] < height[i]) {
      // Get the bottom height of the pool
      const poolBottom = stack.pop();
      // But if stack is empty, there is no left boundary and the loop ends
      if(! stack.length) {break;
      }
      // get the left edge index of the pool
      bottom.push(poolBottom);
      // get the right edge index of the pool
      left.push(stack[stack.length - 1]);
      // Get the bottom index of the pool
      right.push(i);
    }

    stack.push(i);
  }

  // Calculate the summation of pool area iteratively
  for (let i = 0; i < left.length; i++) {
    const leftHeight = height[left[i]];
    const rightHeight = height[right[i]];
    const bottomHeight = height[bottom[i]];

    // Take the minimum value of the left and right boundary - bottom height = pool height
    const accHeight = Math.min(leftHeight, rightHeight) - bottomHeight;
    const width = right[i] - left[i] - 1;
    area += accHeight * width;
  }

  return area;
};

/* Complexity time O(n) Space maximum O(n-2) minimum O(1) */
Copy the code

Method 2:Violence law(Can’t pass just provide ideas)

Train of thought1.Iterate over the height I of each column2.If the left and right boundaries higher than height[I] can be found, the water can be stored. The steps are as follows1.Look for the margin to the left of I, and record leftHeight if there is a margin higher than height[I] and the highest left margin2.Find the right edge of I, and if it is higher than height[I] and the highest right edge is rightHeight3.Calculate height difference curHeight= (MathMin (leftHeight, rightHeight) - height [I])4.Area = curHeight *1(Column height)3.Repeat the above calculation process to find the sum of the areas */var trap = function (height) {
  let area = 0;
  for (let i = 0; i < height.length; i++) {
    let leftHeight = -1;
    // Find the highest left boundary
    for (let j = i; j > -1; j--) {
      if (height[j] > height[i]) {
        leftHeight = Math.max(height[j], leftHeight); }}// Find the highest right boundary
    let rightHeight = -1;
    for (let j = i; j < height.length; j++) {
      if (height[j] > height[i]) {
        rightHeight = Math.max(height[j], rightHeight); }}if (leftHeight === -1 || rightHeight === -1) {
      continue;
    }

    const curHeight = Math.min(leftHeight, rightHeight) - height[i];
    area += curHeight * 1;
  }

  return area;
};

/* Complexity time O(n^2) space O(1) */

Copy the code

conclusion

So this problem is looking at how you apply stack to find the left and right boundaries

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]