一道简单的算法题-接雨水

381 阅读2分钟

积雨问题

题目:求下雨后一个砖型序列能积多少单位的雨

例子:

// 砖型序列
const blocks = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
// 结果:6

pic
pic

分析:木桶原理,针对其中某个节点,其左侧的最高节点和其右侧最高节点(两个节点都高于当前节点),组成的当前节点木桶

当前节点可以积雨量 = 木桶的最短值 - 当前节点高度

思路一: 根据上述分析得到公式

    itemRainCount = min(leftMax, rightMax) - item

上代码

const calculateRain = function(array: number[]) {
  let sum = 0;
  for (let i = 1; i < array.length - 1; i++) {
    let itemLeftMax = array[0];
    for (let leftI = 1; leftI < i; leftI++) {
      itemLeftMax = Math.max(array[leftI], itemLeftMax);
    }

    let itemRightMax = array[i + 1];
    for (let rightI = i + 1; rightI < array.length; rightI++) {
      itemRightMax = Math.max(array[rightI], itemRightMax);
    }

    const itemRain = Math.min(itemLeftMax, itemRightMax) - array[i];
    sum += itemRain > 0 ? itemRain : 0; // 当前节点高与左侧右侧节点
  }
  return sum;
};

思路二:上述思路的时间复杂度为 O(n^2),使用动态规划的方式从当前节点计算左右的增量,增量有效则将其存储下来,将左侧增量与右侧增量对比,去木桶最小值然后剪去当前节点高度就是当前节点的积雨量,照旧,leetcode 上面的图画的很好

pic
pic

上代码

const array = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

const rain = function(array: number[]) {
  let rainSum = 0;
  const leftMax = [array[0]];
  const rightMax = [];
  rightMax[array.length - 1] = array[array.length - 1];
  for (let i = 1; i < array.length; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], array[i]);
  }
  for (let i = array.length - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], array[i]);
  }
  for (let i = 0; i < array.length; i++) {
    rainSum += Math.min(leftMax[i], rightMax[i]) - array[i];
  }
  return rainSum;
};

思路三:上述方法时间复杂度减少到了 O(n), 但是却开辟了两个数组存储增量数据的节点,增加了空间复杂度,下面介绍一种方式来减少空间复杂度 双指针。使用两个指针标记组数两头的节点,对比指针节点的木桶值,向内取遍历节点,取到向左向右移动的增量最大值,然后获取每个节点的积雨量,获取 sum 值。

先上代码:

const array = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

const rain3 = function(array: number[]) {
  let leftMax = 0;
  let rightMax = 0;
  let left = 1;
  let right = array.length - 2;
  let sum = 0;
  for (let i = 1; i < array.length - 1; i++) {
    if (array[left - 1] < array[right + 1]) {
      leftMax = Math.max(leftMax, array[left - 1]);
      if (leftMax > array[left]) {
        sum += leftMax - array[left];
      }
      left++;
    } else {
      rightMax = Math.max(rightMax, array[right + 1]);
      if (rightMax > array[right]) {
        sum += rightMax - array[right];
      }
      right--;
    }
  }
  return sum;
};