水池接雨水的经典问题I&II

https://leetcode.com/problems/trapping-rain-water

https://leetcode.com/problems/trapping-rain-water-ii

这两道题目,一个是一维,一个是二维。都很经典。

基本的做法,可以看这里:

https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue

这个主要针对二维,但是对于一维,也是一个道理。

一维的解法,可以看这里:

https://discuss.leetcode.com/topic/5125/sharing-my-simple-c-code-o-n-time-o-1-space

整体思想是先找到边缘的最矮的,然后就可以计算蓄了多少水了。

而二维的里面,用到了一个priority_queue,这样能够对于一大圈的节点,也能够找到合适的。

原文地址:https://www.cnblogs.com/charlesblc/p/6446528.html