灌水类双指针

题目套路

不同于two sum类问题问的是triple/pair之间的sum关系，灌水类问题一般隐藏含义是找triple,使得 他们的大小满足一定的不等关系，比如trapping rain water, 隐藏含义是找一个slot它左右两边 的wall，所以等同于A[i] > A[j] && A[j] < A[k], 再比如说我面挂Facebook的那道题，直接要找的 就是triple使得A[i] < A[j] < A[k],所以这种问triple之间不等关系的题目很有可能是灌水类问题， 而且一般暴力解就是polynomial级别的（遍历所有情况）。遇见这种题目的解决办法就是灌水类双指针， 记得他也是对撞型哦。

如何使用双指针优化时间空间

• 灌水类双指针的基本款就是开两个helper array，记为left和right。然后分别从左到右和 从右到左去two pass。这样的好处就是以前我们如果要找某一个元素两边的信息，需要O(n), 因为从这个元素出发，分别向两边扩散。但是用了helper array之后，我们每次pass的时候只用 关心一边，而因为我们是从左到右遍历的，所以我们在pass的时候一直记录着元素左边的信息。 到了每个元素的时候，只需要O(1)。所以整体的时间复杂度就降为O(n)。

• 不过上述解法还是用到了O(n)的空间复杂度，对于灌水类问题，很有可能可以不用额外的数组， 这样的话就需要我们能够anchor住左边或者右边的点。这样在pass的时候我们虽然只记录了某一边 的情况，但是因为anchor住的点满足全局的条件，所以我们可以直接算出全局的解。比如trapping rain water里面，我们可以找到一个global wall 这样无论是从左到右还是从右到左pass，都有一边已经 anchor了。

更general的灌水问题

其实像Product of Array Except Self这道题，虽然并没有要求triple/pair，但是还是用到了 灌水类双指针的思想，那就是用O(1)的时间去找到当前元素左右的信息。以往暴力解是需要O(n), 因为我们需要向两边扩散。而用了two pass之后，每次可以focus on只找一边的信息，所以降低了 复杂度。

可以拓展到二维的灌水类解法

上面提到的两种双指针解法都可以很好的解决普通的灌水类问题，但是遇到contain most water 这道题就没办法了。这时取而代之的是另一种方法，那就是从两边往中间灌水。这里头就用到了 木桶原理。我们在一个容器中灌的水取决于他的桶壁里的短板。所以我们每次就需要找到最短的一边 然后从这边灌水。在知道短板的时候，能灌多少水是确定的（不超过短板），而长的那一边并不确定 因为这取决于之后他遇到的其他短板的长度，短板更高可能灌的水也越多。所以灌水类问题另一个的核心思想就是找短板。这放在 一维里面就是两者取其短，放到矩阵里面就是矩阵的边缘取其短（minHeap).

题目

• Leetcode 361. Bomb Enemy (左右各一遍pass，找出此炸弹左边／右边可以炸死的敌人。上下各一遍pass，找出此炸弹上边／下边可以炸死的敌人)
• Leetcode 11. Container With Most Water
• Leetcode 42. Trapping Rain Water
• Leetcode 407. Trapping Rain Water II