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

preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

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

Link: leetcode-cn.com/problems/tr…

Answer key

  1. [I] = min(left, right) -nums [I] = min(left, right) -nums [I] = min(left, right) -nums [I] = min(left, right) -nums [I] = min(right, right) -nums [I] As shown in the figure below, the amount of water that can be stored at cur is min(2, 3) -0 = 2, so the final result is to find the sum of the water that can be stored at all locations. The time complexity of finding the maximum value on the left and right is O(n), so the time complexity of the whole algorithm is O(n²), and the space complexity is O(n). Of course, this method cannot be used in all cases, and the time complexity needs to be reduced.

/ * * *@param {number[]} height
 * @return {number}* /
var trap = function(height) {
    const n = height.length
    let ans = 0
    for (let i = 0; i < n; ++i) {
        l = Math.max(... height.slice(0, i + 1))
        r = Math.max(... height.slice(i)) ans +=Math.min(l, r) - height[i]
    }
    return ans
};
Copy the code
  1. In method 1, we re compare all the values to the left of I at every position, and all the values to the right of I to find the maximum value on both sides, and there is double counting. In fact, we can use the maximum value to the left of I minus one to calculate the maximum value to the left of I every time, just by comparing the maximum value to the left of I minus one to the size of I. The same goes for the right-hand side, so you can have two arrays, left and right, which are the maximum from 0 to n-1, and the minimum from n-1 to 0. It’s also a space-for-time strategy. See the specific code below. It’s O(n) in time, and O(n) in space.
/ * * *@param {number[]} height
 * @return {number}* /
var trap = function(height) {
    const n = height.length
    let left = []
    let right = []
    for (let i = 0; i < n; ++i) {
        left[i] = i === 0 ? height[i] : Math.max(left[i-1], height[i])
    }
    for (let i = n - 1; i >= 0; --i) {
        right[i] = i === n - 1 ? height[i] : Math.max(right[i+1], height[i])
    }
    
    let ans = 0
    for (let i = 0; i < n; ++i) {
        ans += Math.min(left[i], right[i]) - height[i]
    }
    return ans
};
Copy the code
  1. Double pointer method. According to the principle of the barrel, the amount of water is only determined by the short side. We define two Pointers l and r, and two variables max_l and max_r, and initialize them to the values at both ends. Max_l = Max (max_l, height[I]); max_r = Max (max_l, height[I]); max_r = Max (max_l, height[I]); In fact, this algorithm is essentially an optimized version of Algorithm 2, where we calculate the maximum values of the left and right sides of I as we approach from both sides to the middle, while algorithm 2 calculates the maximum values of both sides in advance. See the specific code below. The time complexity is O(n), the space complexity is O(1)
/ * * *@param {number[]} height
 * @return {number}* /
var trap = function(height) {
    const n = height.length
    let l = 0
    let r = n - 1
    max_l = height[l]
    max_r = height[r]
    let ans = 0
    while (l < r) {
        if (max_l < max_r) {
            ans += max_l - height[l]
            ++l
            max_l = Math.max(max_l, height[l])
        } else {
            ans += max_r - height[r]
            --r
            max_r = Math.max(max_r, height[r])
        }
    }
    return ans
};
Copy the code
  1. When the height[I] value is larger than the corresponding height of the top of the stack, it indicates that a container can be constructed to hold water, just pop the top of the stack element. The top of the stack element and the current position of I can construct a container. By calculating the width and height of the container, you can know how much water is in it. See the following code for details. O(n) time, O(n) space
/ * * *@param {number[]} height
 * @return {number}* /
var trap = function(height) {
    const n = height.length
    let stack = []
    let ans = 0
    for (let i = 0; i < n; ++i) {
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const cur = stack.pop()
            if (stack.length === 0) break
            const l = stack[stack.length - 1]
            const w = i - l - 1
            const h = Math.min(height[l], height[i]) - height[cur]
            ans += h * w
        }
        stack.push(i)
    }
    return ans
};
Copy the code