leetcode42：接雨水问题

[sisterAn]

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

leetcode

[latte03]

暴力解法

// 获取最大高度
function getMaxHeight(array) {
  let maxHeight = 0;
  array.forEach((element) => {
    if (element > maxHeight) maxHeight = element;
  });
  return maxHeight;
}
// 获取正数，可以设置默认值
function getPositiveNumber(number, def) {
  return number < 0 ? (def ? def : 0) : number;
}

function trap(height) {
  if (lenght === 0) return 0;

  let total = 0;

  for (let i = 0; i < lenght; i++) {
    const leftMax = getMaxHeight(height.slice(0, i));
    const rightMax = getMaxHeight(height.slice(i + 1, lenght));
    total += getPositiveNumber(Math.min(leftMax, rightMax) - height[i]);
  }
  return total;
}

双指针

function trap(height) {
  let total = 0;
  let left = 0,
    right = height.length - 1,
    leftMax = 0,
    rightMax = 0;
  while (left <= right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    if (leftMax < rightMax) {
      total += leftMax - height[left];
      left++;
    } else {
      total += rightMax - height[right];
      right--;
    }
  }
  return total;
}

[AnranS]

栈

var trap = function (height) {
    let stack = [];
    let index = 0;
    let sumArea = 0;
    while (index < height.length) {
        while (stack.length !== 0 && height[index] > height[stack[stack.length - 1]]) {
            let h = height[stack[stack.length - 1]];
            stack.pop();
            if (stack.length === 0) break;
            let w = index - stack[stack.length - 1] - 1;
            let min = Math.min(height[stack[stack.length - 1]], height[index]);
            sumArea += (min - h) * w;
        }
        stack.push(index);
        index++;
    }
    return sumArea;
};

[Forever17s]

双指针，中间向两边扩展

var trap = function(height) {
  if(height.length <= 1) return 0;

  const getMax = (list) => {
      if (!list.length) return 
      let maxIndex = 0
      for(let i = 1; i < list.length; i ++) {
          if(list[i] > list[maxIndex]) maxIndex = i
      }
      return maxIndex
  }

  let maxLeft = maxRight = getMax(height);
  let sum = 0;

  while(maxLeft > 0) {
      let temp = getMax(height.slice(0, maxLeft))
      for(let i = temp; i < maxLeft; i ++){
          sum += height[temp] - height[i]
      }
      maxLeft = temp
  }

  while(maxRight < height.length - 1) {
      let temp = getMax(height.slice(maxRight + 1, height.length)) + maxRight + 1
      for(let i = maxRight + 1; i < temp; i ++){
          sum += height[temp] - height[i]
      }
      maxRight = temp
  }

  return sum
};

[lewisYe]

暴力

var trap = function(height) {
    let len = height.length
    if(!len)return 0
    let sum = 0
    for(let i=0;i<len;i++){
        let leftA = []
        let leftB = []
        for(let n=0;n<i;n++){
            leftA.push(height[n])
        }
        for(let n=i+1;n<len;n++){
            leftB.push(height[n])
        }
        let leftMax = leftA.length ? Math.max.apply(null,leftA) : 0
        let rightMax = leftB.length ? Math.max.apply(null,leftB) : 0
         
        sum += Math.min(leftMax,rightMax) - height[i] > 0 ? Math.min(leftMax,rightMax) - height[i] : 0
    }
    return sum
};

这个leetcode 上超时了 优化一下如下

var trap = function(height) {
    let len = height.length
    if(!len)return 0
    let sum = 0
    for(let i=0;i<len;i++){
        let leftA = []
        let leftB = []
        let leftMax= -1;
        let rightMax = -1
        for(let n=0;n<i;n++){
            if(height[n] > leftMax){
                leftMax = height[n]
            }
        }
        for(let n=i+1;n<len;n++){
            if(height[n] > rightMax){
                rightMax = height[n]
            }
        }
        sum += Math.min(leftMax,rightMax) - height[i] > 0 ? Math.min(leftMax,rightMax) - height[i] : 0
    }
    return sum
};

[JohnApache]

可能用的指针比较多，基本原理也是双指针，做了一个右边双指针为了补全左双指针无法覆盖到的位置，应该有优化的空间

const trap = (height: number[]) => {
    const len = height.length;
    if (len <= 2) return 0;
    let slowLeftPos = 0;
    let fastLeftPos = 0;
    let slowRightPos = len - 1;
    let fastRightPos = len - 1;
    let result = 0;
    let currentTotalHeight = 0;
    while (fastLeftPos < len) {
        const slowLeftHeight = height[slowLeftPos];
        const fastLeftHeight = height[fastLeftPos];
        if (!slowLeftHeight) {
            slowLeftPos++;
            fastLeftPos++;
            continue;
        }
        if (slowLeftPos === fastLeftPos || slowLeftHeight > fastLeftHeight) {
            currentTotalHeight += fastLeftHeight;
            fastLeftPos++;
            continue;
        }

        result += (fastLeftPos - slowLeftPos) * slowLeftHeight - currentTotalHeight;
        slowLeftPos = fastLeftPos; // 移动左慢指针至左快指针位置
        currentTotalHeight = 0;
    }

    currentTotalHeight = 0; // 重制 currentTotalHeight

    while (fastRightPos >= slowLeftPos) {
        const slowRightHeight = height[slowRightPos];
        const fastRightHeight = height[fastRightPos];
        if (!slowRightHeight) {
            slowRightPos--;
            fastRightPos--;
            continue;
        }
        if (slowRightPos === fastRightPos || slowRightHeight > fastRightHeight) {
            currentTotalHeight += fastRightHeight;
            fastRightPos--;
            continue;
        }

        result += (slowRightPos - fastRightPos) * slowRightHeight - currentTotalHeight;
        slowRightPos = fastRightPos; // 移动右慢指针至右快指针位置
        currentTotalHeight = 0;
    }

    return result;
};