暴力解法

对于数组中的每个元素，找出下雨水后能达到的最高位置，等于两边高度的较小值减去当前高度的值。

时间复杂度O(n^2)，空间复杂度O(1)

• Runtime: 176 ms, faster than 5.64%
• Memory Usage: 38.6 MB, less than 5.99%

var trap = function(height) {
    var res = 0
    for(var i = 1; i < height.length - 1; i++){
        var l = 0
        var r = 0
        for(var j = i; j >= 0; j--){
            l = Math.max(l, height[j])
        }
        for(var j = i; j < height.length; j++){
            r = Math.max(r, height[j])
        }
        res = res + Math.min(l, r) - height[i]
    }
    return res
};

动态规划

在找左边第i个最大元素的时候，要用到第i-1次的结果，将之前比较的结果存储下来。
时间复杂度O(n)，空间复杂度O(n)

• Runtime: 100 ms, faster than 26.34%
• Memory Usage: 41 MB, less than 5.99%

var trap = function(height) {
    var res = 0
    var left = []
    var right = []
    var n = height.length 
    left[0] = height[0]
    right[n - 1] = height[n - 1]
    for(var i = 1; i < height.length; i++){
        left[i] = Math.max(left[i - 1], height[i])
    }
    
    for(var i = n - 2; i >= 0; i--){
        right[i] = Math.max(right[i + 1], height[i])
    }
    for(var i = 1; i < n - 1; i++){
        res += Math.min(left[i], right[i]) - height[i]
    }
    return res
};

双指针法

时间复杂度O(n)，空间复杂度O(1)

• Runtime: 84 ms, faster than 82.73%
• Memory Usage: 39.1 MB, less than 5.99%

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let res = 0
  let l_max = 0
  let r_max = 0
  let left = 0
  let right = height.length - 1
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] > l_max) {
        l_max = height[left]
      } else {
        res += l_max - height[left] 
      }
      left++
    } else {
      if (height[right] > r_max) {
        r_max = height[right]
      } else {
        res += r_max - height[right] 
      }
      right--
    }
  }
  return res
};