42.接雨水

链接：42.接雨水
难度：Hard
标签：栈、数组、双指针、动态规划、单调栈
简介：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

题解 1 - javascript

• 编辑时间：2020-04-08
• 执行用时：84ms
• 内存消耗：36.1MB
• 编程语言：javascript
• 解法介绍：先算出每个点的左高和右高，再通过判断两边高度来判断是否储水。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let max = 0;
  let volumn = 0;
  const leftMax = [];
  const rightMax = [];
  for (let i = 0; i < height.length; i++) {
    leftMax[i] = max = Math.max(height[i], max);
  }
  max = 0;
  for (let i = height.length - 1; i >= 0; i--) {
    rightMax[i] = max = Math.max(height[i], max);
  }
  for (let i = 0; i < height.length; i++) {
    volumn += Math.min(leftMax[i], rightMax[i]) - height[i];
  }
  return volumn;
};

题解 2 - typescript

• 编辑时间：2021-07-20
• 执行用时：88ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：逐层增加。

function trap(height: number[]): number {
  const n = height.length;
  const stack: number[] = [];
  let ans = 0;
  for (let i = 0; i < n; i++) {
    const h = height[i];
    while (stack.length && height[stack[stack.length - 1]] < h) {
      const cur = stack.pop()!;
      if (stack.length === 0) continue;
      const left = stack[stack.length - 1];
      ans += (Math.min(height[left], h) - height[cur]) * (i - left - 1);
    }
    stack.push(i);
  }
  return ans;
}

题解 3 - typescript

• 编辑时间：2021-07-22
• 执行用时：80ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：按列求出每一列接水量。

function trap(height: number[]): number {
  const n = height.length;
  const l = new Array(n).fill(0);
  const r = new Array(n).fill(0);
  let max = height[0];
  for (let i = 1; i < n; i++) {
    l[i] = max;
    max = Math.max(max, height[i]);
  }
  max = height[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    r[i] = max;
    max = Math.max(max, height[i]);
  }
  let ans = 0;
  for (let i = 0; i < n; i++) ans += Math.max(Math.min(l[i], r[i]) - height[i], 0);
  return ans;
}

题解 4 - typescript

• 编辑时间：2021-07-22
• 执行用时：80ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：合并循环。

function trap(height: number[]): number {
  const n = height.length;
  const l = new Array(n).fill(0);
  const r = new Array(n).fill(0);
  let maxL = height[0];
  let maxR = height[n - 1];
  for (let i = 1; i < n - 1; i++) {
    l[i] = maxL;
    maxL = Math.max(maxL, height[i]);
    r[n - 1 - i] = maxR;
    maxR = Math.max(maxR, height[n - 1 - i]);
  }
  let ans = 0;
  for (let i = 0; i < n; i++) ans += Math.max(Math.min(l[i], r[i]) - height[i], 0);
  return ans;
}

题解 5 - cpp

• 编辑时间：2023-07-23
• 执行用时：16ms
• 内存消耗：19.6MB
• 编程语言：cpp
• 解法介绍：统计左右最大高度。

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0, n = height.size();
        vector<int> r(n, 0);
        for (int i = n - 1, cur = 0; i >= 0; i--) {
            r[i] = cur;
            cur = max(cur, height[i]);
        }
        for (int i = 0, cur = 0; i < n; i++) {
            cur = max(cur, height[i]);
            sum += max(0, min(cur, r[i]) - height[i]);
        }
        return sum;
    }
};

题解 6 - python

• 编辑时间：2023-07-23
• 执行用时：68ms
• 内存消耗：17.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def trap(self, height: List[int]) -> int:
        sum = 0
        n = len(height)
        cur = 0
        r = [0] * n
        for i in range(n-1, -1, -1):
            r[i] = cur
            cur = max(cur, height[i])
        cur = 0
        for i in range(n):
            cur = max(cur, height[i])
            sum += max(0, min(cur, r[i])-height[i])
        return sum

题解 7 - rust

• 编辑时间：2023-07-23
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut sum = 0;
        let n = height.len();
        let mut cur = 0;
        let mut r = vec![0; n];
        for i in (0..n).rev() {
            r[i] = cur;
            cur = cur.max(height[i]);
        }
        cur = 0;
        for i in 0..n {
            cur = cur.max(height[i]);
            sum += 0.max(cur.min(r[i]) - height[i]);
        }
        sum
    }
}