Question 42 is from Leetcode. Solution method and code from leetcode solution analysis.

Topic describes

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] output: 6Copy the code

Example 2:

Height = [4,2,0,3,2,5Copy the code

Tip:

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
Copy the code

Thinking method

  1. Dynamic programming
  • Finds the highest bar block height from subscript I to the left end of the array{left_max}.
  • Find the highest bar block height in the array from subscript I to the rightmost end{right_max}.
  • The scanning array{height}.
  • Math.min({max_left}, {max_right}) – {height} to ans.

Code demo

Method 1: dynamic programming

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  const len = height.length;
  if (len < 3) return 0;
  const left = [];
  const right = [];
  left[0] = height[0];
  right[len - 1] = height[len - 1];
  let res = 0;
  for (let i = 1; i < len; i++) {
    left[i] = Math.max(left[i - 1], height[i]);
  }
  for (let i = len - 2; i >= 0; i--) {
    right[i] = Math.max(right[i + 1], height[i]);
  }
  for (let i = 0; i < len; i++) {
    res += Math.min(left[i], right[i]) - height[i];
  }
  return res;
};
Copy the code

Complexity analysis:

Time complexity: O(n).

Store the maximum height array, traversing it twice, O(n) each time. Finally, ans, O(n) is updated with stored data.Copy the code

Space complexity: O(n).

Compared to method 1, extra O(n) space is used to place left_max and right_max arrays.Copy the code

Method two: stack

/** * @param {number[]} height * @return {number} */ var trap = function(height) { if (height.length < 3) return 0; const len = height.length; const stack = []; let res = 0, i = 0; while (i < len) { while (stack.length && height[i] > height[stack[stack.length - 1]]) { const top = stack.pop(); if (! stack.length) break; const width = i - stack[stack.length - 1] - 1; const depth = Math.min(height[i], height[stack[stack.length - 1]]) - height[top]; res += width * depth; } stack.push(i++); } return res; };Copy the code

Complexity analysis:

Time complexity: O(n).

Space complexity: O(n).

Method three: double pointer

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  if(height.length < 3) return 0;
  let left = 0, right = height.length - 1;
  let left_max = 0, right_max = 0, res = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] > left_max) {
        left_max = height[left];
      } else {
        res += left_max - height[left];
      }
      left++;
    } else {
      if (height[right] > right_max) {
        right_max = height[right];
      } else {
        res += right_max - height[right];
      }
      right--;
    }
  } 
  return res;
}
Copy the code

Complexity analysis:

Time complexity: O(n).

Space complexity: O(1).

conclusion

Three programming ideas need to be well understood and digested. In terms of performance, the third method has better space complexity.