Leetcode难度Hard，其实没你想的那么难

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/trapping-rain-water著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

挺有意思的一个题目，日常生活中也到处可见这样的例子。如果我们一格一格从左往右看，能够蓄水的圆柱必定存在下面这样的情况，在它的左边有比它更高的圆柱，在它的右边也有比他更高的圆柱，它最终所能蓄水的大小等于，左右两个比他更高的圆柱中，小的那一个与它本身的高度差。

我们用l[i]表示第i个圆柱左边最高的圆柱高度，用r[i]表示它右边最高的圆柱的高度，那么，圆柱i的蓄水量为min{l[i], r[i]} >= h[i] ？min{l[i], r[i]} - h[i] : 0。那么，求一个序列的最左边的做大值，最右边的最大值，我们已经在很多不同的算法题当中遇见过了，这是一个常见的算法套路，我们可以从左往右枚举，用递推的套路，求出l[i]，同理，从右往左，求出r[i]。这些都是可以在O(n)的算法复杂度里面解决的。

不过我昨天做这个题目的时候，想到的并不是这种解法，对于一个常年刷题的人来说，看到这样的问题，自然而然的想到的解法就是单调问题。我们可以把这个图沿着最高点拆成2部分，当装满水的时候，必然会成为阶梯形状的，所以，我们只要去找到这个阶梯形状的各个拐点即可。也就是先找到最高点，然后找到次高点，接着找到第三高点。

按照上述的思路，我们先找到最高点，然后逐渐去寻找阶梯的拐角点。这里有两种算法，第一种是先排序，我们按照高度优先，进行排序，我们用tmp来记录上一个高点的位置，如果当前高度的坐标大于上一个高点，那么不予考虑，直接丢弃，否则，说明上一个高点到当前点的最大蓄水高度为h[i]，遍历计算出最终的蓄水量。

另外一种做法，要去找到所有阶梯的拐点，由于是阶梯形状的，所以，我们可以维护一个单调栈进行解决。什么是单调栈呢？就是栈底到栈顶的值的大小是单调递增或者递减的。维护单调栈的方法非常的简单，就是当当前值小于栈顶的时候，直接入栈。当大于栈顶的时候，栈顶不断出栈，直到栈为空或者小于栈顶元素。与之非常相似的，有单调队列。后续我们有机会会继续讲一讲。

当然，这个题目还有很多种不同的做法，甚至可以不用寻找最高点也可以用栈解决。不过我觉得上述两种方法都是最直观跟容易理解的。不知道你有没有其他不同的解法，一起交流，共同进步。