problem0042

package
v0.0.0-...-899dd15 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Sep 11, 2020 License: MIT Imports: 0 Imported by: 0

README

42. Trapping Rain Water

题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. rainwatertrap

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

解题思路

解题的关键有两点

  1. 理解 i 点的存水量为 min(max(height[:i+1]...), max(height[i:]...)) - height[i]
  2. 高效地找到 max(height[:i+1]...) 和 max(height[i:]...)

总结

利用记录,比每次现找要省时的多。

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL