42.接雨水
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后接多少雨水。
图一是由数组[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
思路：
1. 找到最大值所在的索引
2. 找到所有的顶点索引
注1：定点索引处的值比相邻两个数大（或等于），并且在最大值左边升序，在最大值右边降序；
注2：最大值左边的顶点需从左往右寻找，最大值右边的顶点需从右往左寻找，否则右边部分的索引会有问题；
3. 根据所有的顶点索引计算水量
具体细节见注释。
反思：虽然时间复杂度还行，但是代码写的太复杂了，不容易阅读。leetcode上同样复杂度的代码更加简洁，像他们看齐。
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后接多少雨水。
图一是由数组[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
思路：
1. 找到最大值所在的索引
2. 找到所有的顶点索引
注1：定点索引处的值比相邻两个数大（或等于），并且在最大值左边升序，在最大值右边降序；
注2：最大值左边的顶点需从左往右寻找，最大值右边的顶点需从右往左寻找，否则右边部分的索引会有问题；
3. 根据所有的顶点索引计算水量
具体细节见注释。
反思：虽然时间复杂度还行，但是代码写的太复杂了，不容易阅读。leetcode上同样复杂度的代码更加简洁，像他们看齐。
展开
评论
3
![[不失礼貌的微笑]](http://lf3-cdn-tos.bytescm.com/obj/static/xitu_juejin_web/img/jj_emoji_16.9d17f6d.png)
。大家看评论。我是代码给篮子发不发呢？