变形题

1. Valid Triangle Number
2. Container With Most Water
3. Trapping Rain Water
4. Trapping Rain Water II
5. Maximum Distance in Arrays
6. Sort Transformed Array
7. Max Consecutive Ones II

1. Valid Triangle Number

两边之和大于第三边 + 2 pointers在i 的左边

类似的做法，不同的是，两个指针都在左边，且left从最小开始，right从最大数开始。只要left + right > 第三边就可以了，那么right和[left 到 right]之间的数都可以组成valid combination。所以count += right - left。

O(n^2)

2. Container With Most Water

3. Trapping Rain Water

5. Maximum Distance in Arrays

1. min heap + max heap (要记录array index)
2. keep track of min and max

两个值不能是同一个array的。一开始的想法是两个指针，保存最大值和最小值就好了。可是，如下例子会错误

{
{1, 4},
{0, 5},
{2, 4}
}

指针会同时使用第二个array的，但是题目不允许。

所以用两个变量start和end分别表示当前遍历过的数组中最小的首元素，和最大的尾元素，那么每当我们遍历到一个新的数组时，只需计算新数组尾元素和start绝对差，跟end和新数组首元素的绝对差，取二者之间的较大值来更新结果res。

5 - 1，4 - 0，一直都是两个数组交叉相减，所以保证了两个数不是同一行的。

也可以用heap来做，就是得保证两个数不是同一行的，所以得记录行数。

6. Sort Transformed Array

单调性 + 从两个头开始还是从中间开始取决于a的正负值

注意：如果是a = 0的话，同a > 0的情况是一样的。都是从两头开始。