力扣00042.接雨水

发表于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 7 分钟
接雨水、栈、数组、双指针、动态规划、单调栈、困难

题目描述

给定 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
  • $1 <= n <= 2 * 10^4$
  • $0 <= height[i] <= 10^5$

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() < 3) {
            return 0;
        }
        int left = 0, right = height.size() - 1;
        int left_max = 0, right_max = 0;
        int result = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    result += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    result += right_max - height[right];
                }
                right--;
            }
        }
        return result;
    }
};

结果

执行用时 : 15 ms, 击败 50.80% 使用 C++ 的用户

内存消耗 : 21.66 MB, 击败 17.09% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int trap(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0;
        int result = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    result += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    result += right_max - height[right];
                }
                right--;
            }
        }
        return result;
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 45.56 MB, 击败 5.11% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) < 3:
            return 0
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        result = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    result += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    result += right_max - height[right]
                right -= 1
        return result

结果

执行用时 : 18 ms, 击败 99.40% 使用 Python 的用户

内存消耗 : 12.68 MB, 击败 91.49% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        result = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    result += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    result += right_max - height[right]
                right -= 1
        return result

结果

执行用时 : 47 ms, 击败 94.36% 使用 Python3 的用户

内存消耗 : 17.77 MB, 击败 74.44% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int trap(int* height, int heightSize) {
    if (heightSize < 3) {
        return 0;
    }
    int left = 0, right = heightSize - 1;
    int left_max = 0, right_max = 0;
    int result = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                result += left_max - height[left];
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                result += right_max - height[right];
            }
            right--;
        }
    }
    return result;
}

结果

执行用时 : 9 ms, 击败 69.17% 使用 C 的用户

内存消耗 : 6.44 MB, 击败 99.08% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int Trap(int[] height) {
        if (height.Length < 3) {
            return 0;
        }
        int left = 0, right = height.Length - 1;
        int left_max = 0, right_max = 0;
        int result = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    result += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    result += right_max - height[right];
                }
                right--;
            }
        }
        return result;
    }
}

结果

执行用时 : 76 ms, 击败 95.76% 使用 C# 的用户

内存消耗 : 44.57 MB, 击败 26.25% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if (height.length < 3) {
        return 0;
    }
    let left = 0, right = height.length - 1;
    let left_max = 0, right_max = 0;
    let result = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                result += left_max - height[left];
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                result += right_max - height[right];
            }
            right--;
        }
    }
    return result;
};

结果

执行用时 : 52 ms, 击败 99.07% 使用 JavaScript 的用户

内存消耗 : 50.02 MB, 击败 25.70% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function trap(height: number[]): number {
    if (height.length < 3) {
        return 0;
    }
    let left: number = 0, right: number = height.length - 1;
    let left_max: number = 0, right_max: number = 0;
    let result: number = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                result += left_max - height[left];
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                result += right_max - height[right];
            }
            right--;
        }
    }
    return result;
}

结果

执行用时 : 70 ms, 击败 72.92% 使用 TypeScript 的用户

内存消耗 : 52.29 MB, 击败 29.22% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

    /**
     * @param Integer[] $height
     * @return Integer
     */
    function trap($height) {
        $length = count($height);
        if ($length < 3) {
            return 0;
        }
        $left = 0;
        $right = $length - 1;
        $left_max = 0;
        $right_max = 0;
        $result = 0;
        while ($left < $right) {
            if ($height[$left] < $height[$right]) {
                if ($height[$left] >= $left_max) {
                    $left_max = $height[$left];
                } else {
                    $result += $left_max - $height[$left];
                }
                $left++;
            } else {
                if ($height[$right] >= $right_max) {
                    $right_max = $height[$right];
                } else {
                    $result += $right_max - $height[$right];
                }
                $right--;
            }
        }
        return $result;
    }
}

结果

执行用时 : 30 ms, 击败 65.31% 使用 PHP 的用户

内存消耗 : 21.50 MB, 击败 79.59% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    func trap(_ height: [Int]) -> Int {
        let length = height.count
        guard length >= 3 else {
            return 0
        }
        var left = 0
        var right = length - 1
        var leftMax = 0
        var rightMax = 0
        var result = 0
        while left < right {
            if height[left] < height[right] {
                if height[left] >= leftMax {
                    leftMax = height[left]
                } else {
                    result += leftMax - height[left]
                }
                left += 1
            } else {
                if height[right] >= rightMax {
                    rightMax = height[right]
                } else {
                    result += rightMax - height[right]
                }
                right -= 1
            }
        }
        return result
    }
}

结果

执行用时 : 26 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 15.84 MB, 击败 7.33% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    fun trap(height: IntArray): Int {
        val length = height.size
        if (length < 3) {
            return 0
        }
        var left = 0
        var right = length - 1
        var leftMax = 0
        var rightMax = 0
        var result = 0
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left]
                } else {
                    result += leftMax - height[left]
                }
                left++
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right]
                } else {
                    result += rightMax - height[right]
                }
                right--
            }
        }
        return result
    }
}

结果

执行用时 : 189 ms, 击败 98.29% 使用 Kotlin 的用户

内存消耗 : 39.59 MB, 击败 43.59% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  int trap(List<int> height) {
    if (height.length < 3) {
      return 0;
    }
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int result = 0;
    while (left < right) {
      if (height[left] < height[right]) {
        if (height[left] >= leftMax) {
          leftMax = height[left];
        } else {
          result += leftMax - height[left];
        }
        left++;
      } else {
        if (height[right] >= rightMax) {
          rightMax = height[right];
        } else {
          result += rightMax - height[right];
        }
        right--;
      }
    }
    return result;
  }
}

结果

执行用时 : 284 ms, 击败 88.89% 使用 Dart 的用户

内存消耗 : 148.19 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func trap(height []int) int {
    if len(height) < 3 {
        return 0
    }
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    result := 0
    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                result += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                result += rightMax - height[right]
            }
            right--
        }
    }
    return result
}

结果

执行用时 : 10 ms, 击败 41.46% 使用 Go 的用户

内存消耗 : 5.18 MB, 击败 99.69% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# @param {Integer[]} height
# @return {Integer}
def trap(height)
  return 0 if height.length < 3
  left = 0
  right = height.length - 1
  left_max = 0
  right_max = 0
  result = 0
  while left < right
    if height[left] < height[right]
      if height[left] >= left_max
        left_max = height[left]
      else
        result += left_max - height[left]
      end
      left += 1
    else
      if height[right] >= right_max
        right_max = height[right]
      else
        result += right_max - height[right]
      end
      right -= 1
    end
  end
  result
end

结果

执行用时 : 61 ms, 击败 % 使用 Ruby 的用户

内存消耗 : 207.34 MB, 击败 % 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
object Solution {
  def trap(height: Array[Int]): Int = {
    if (height.length < 3) {
      0
    } else {
      var left = 0
      var right = height.length - 1
      var leftMax = 0
      var rightMax = 0
      var result = 0
      while (left < right) {
        if (height(left) < height(right)) {
          if (height(left) >= leftMax) {
            leftMax = height(left)
          } else {
            result += leftMax - height(left)
          }
          left += 1
        } else {
          if (height(right) >= rightMax) {
            rightMax = height(right)
          } else {
            result += rightMax - height(right)
          }
          right -= 1
        }
      }
      result
    }
  }
}

结果

执行用时 : 548 ms, 击败 81.82% 使用 Scala 的用户

内存消耗 : 56.33 MB, 击败 90.91% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        if height.len() < 3 {
            return 0;
        }
        let mut left = 0;
        let mut right = height.len() - 1;
        let mut left_max = 0;
        let mut right_max = 0;
        let mut result = 0;
        while left < right {
            if height[left] < height[right] {
                if height[left] >= left_max {
                    left_max = height[left];
                } else {
                    result += left_max - height[left];
                }
                left += 1;
            } else {
                if height[right] >= right_max {
                    right_max = height[right];
                } else {
                    result += right_max - height[right];
                }
                right -= 1;
            }
        }
        result
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.10 MB, 击败 92.50% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户