https://leetcode-cn.com/problems/trapping-rain-water/ 栈、数组、双指针

暴力法

我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值

  • 时间复杂度 O(n ** 2)

  • 空间复杂度 O(1) 的额外空间

    1. function trap(height: number[]): number {
    2.   let res = 0;
    3.   let len = height.length;
    4.   for(let i = 0; i < len - 1; i++) {
    5.       let max_left = 0
    6.       let max_right = 0
    7.       for(let j = i; j >=  0; j--) {
    8.           max_left = Math.max(max_left, height[j]);
    9.       }
    10.       for(let j = i; j < len; j++) {
    11.           max_right = Math.max(max_right, height[j]);
    12.       }
    13.       res += Math.min(max_left, max_right) - height[i];
    14.   }
    15.   return res
    16. };

    动态编程

    上一个方法的加强版n
    【42】接雨水：困难 - 图1

  • 时间复杂度 O(n)

  • 空间复杂度 O(n) 的额外空间
    function trap(height: number[]): number {
  if(!height.length) return 0
  let res = 0;
  let len = height.length
  let left_max = []
  let right_max = []
  left_max[0] = height[0]
  right_max[len - 1] = height[len - 1]
  for(let i = 1; i < len; i++) {
      left_max[i] = Math.max(height[i], left_max[i - 1])
  }
  for(let i = len - 2; i >= 0; i--) {
      right_max[i] = Math.max(height[i], right_max[i + 1])
  }
  for(let i = 1; i < len - 1; i++) {
      res += Math.min(left_max[i], right_max[i]) - height[i];
  }
  return res
};

    双指针

    function trap(height: number[]): number {
  let left = 0
  let right = height.length - 1
  let res = 0
  let left_max = 0
  let right_max = 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
};