Trapping Rain Water
大致描述: 给出一个数组, 按如上所述, 求出蓝色方块的数量
(就像一个山脉一样, 看这样的山脉降雨后能留下多少水)
我的思路:
排错:
- 必须有3个以上的山脉才有可能有积水, 所以数组长度必定大于3
- 左右为平地的数组下标截断, 直到有山脉为止
做法:
- 从左到右依次拿到符合条件的格子下标(比如第一次是(1, 3) )
- 计算改区域的雨水
- 重复第一步, 直到结束
// 具体代码在42_.txt中
dalao的思路
// 具体代码在42_2.txt中
分析:
一个格子中能不能存水取决于左右格子的高度
算法从左到右一次, 从有到左一次.
每次假设该格子以左/右单方面最大能放多少水
将同一格的两次数据求最小, 这就是该下标实际能存多少水
最后减去本身的实体格子, 也就得到了空下的格子
算法复杂度为O(n)