Leetcode 0042 trapping-rain-water

非常经典的题。除了暴力解法外，有三种效率比较高的解法：

1. 动态规划
2. 双指针
3. 单调栈

核心

这道题的核心很简单，我们判断一个位置能容纳多少雨水，就是做一个计算。这个计算就是用这个位置，它左边最高的柱子的高度和右边最高的柱子的高度进行对比，找出矮的那一个，然后再减去这个位置本身的高度，我们就可以获得这个位置它能容纳多少雨水。那么实际上我们真正要解决的问题就是如何找到一个位置左边和右边最高的柱子的高度。

动态规划

动态规划的思想是先整体遍历两遍，找出每个位置左边和右边的柱子最高高度，然后再去整体的遍历一遍，计算这个位置它能容纳多少雨水。

双指针

双指针是这道题的最优解法，我们可以发现动态规划中，实际上我们不需要维护整个最高高度的数组。我们其实只需要用左右两个指针，如果发现指针位置出现了一侧最高高度比另一侧矮或相等的情况，就可以判断这个位置能容纳多少雨水。

单调栈

单调栈是这类题的通用解法。我们维护一个从栈底到栈顶递减的栈，就可以判断出在获取到新位置的高度时，前面的哪些高度可以计算出其能容纳的容量。