LeetCode算法学习总结-困难

接雨水问题leetcode42

从左侧看，找到每个对应可以看到最高的柱子，右侧也是，然后遍历数组，只有当当前的柱子低于左侧和右侧的柱子时才能接住雨水（否则有一侧就会漏水），最后将所有的雨水加起来

var trap = function(height) {
  const len = height.length
  let volumn = 0
  if (len < 2) {
    return 0
  }
  const leftMax = []
  const rightMax = []
  let max = 0
  // 从左侧看找到最每个地方对应能看到最高的柱子[ 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3 ]
  for(let i=0; i<len; i++) {
    leftMax[i] = max = Math.max(max, height[i])
  }
  
  max = 0
  // 从右侧看，找到每个地方能看到的对应最高的柱子[ 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1 ]
  for (let i = len - 1; i >=0; i--) {
    rightMax[i] = max = Math.max(max, height[i])
  }

  for (let i = 0; i < len-1; i++) {
    // 站在当前柱子上，必须要低于左侧和右侧最高的柱子，此处才能存住雨水
    if (leftMax[i] > height[i] && rightMax[i] > height[i]) {
      // 左侧和右侧最高柱子中最小的那个-当前柱子的高度=当前柱子能够存放的雨水
      volumn += Math.min(leftMax[i], rightMax[i]) - height[i]
    }
    
  }
  return volumn
};
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));

盛最多水的容器leetcode11

借用双指针来减少搜索空间,参考

• 如果左边低，将i右移
• 如果右边低，将j左移

const maxArea = function(height) {
    let max = 0; // 最大容纳水量
    let left = 0; // 左
    let right = height.length - 1; // 右
    
    while (left < right) {
        // 计算当前水量
        let cur = (right - left) * Math.min(height[left], height[right]);
        max = Math.max(cur, max);
        height[left] < height[right] ? left ++ : right --;
    }

    return max;
};

小红包免费领

小礼物走一走