Two Pointers

需要先排序。

• 适用于
  • 找重复/intersection
  • 把O(n^2)的优化成O(n)
• 如果中间存在重复的值需要循环跳过
• while中的while要保持left<right，保持這個判斷
• 如果要的unique的解（不能重复用）需要while跳过

对型撞指针

Two Sum类型

通过两个指针，变成O(n)，可以证明有些多态不用扫描

if (A[i] + A[j] > sum) {
    j--;
    do sth;
} else if (A[i] + A[j] < sum) {
    i++;
    do sth;
} else {
    i++; or j--;
    do sth;
}

灌水类

• 先找左右两端的柱子，确定了基本线
• 然后往内找
  • 如果高度降低，那么灌水面积肯定减少，可以排除
  • 如果高度增大，则要进行判断
  • 取左右两端较短的不变，将另一边柱子往内部移动，那么总的面积肯定会小于基本面积。所以只可能移动较短的那一侧柱子。
  • 只会遍历数组一次O(n), 一般都是O(n),需要排序的话，用O(nlogn)

    if (A[i] > A[j]) 
    j--;
    else if (A[i] < A[j]) 
    i++;
    else 
    i++; or j--;
    

Container with most water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. 只与左右两边的高度有关，与中间无关

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length < 2) return 0;
        int area = 0; 
        int left = 0;
        int right = len - 1;
        while (left < right) {
            area = Math.max(Math.min(height[left], height[right]) * (right-left), area);

            if (height[left] < height[right])
                left++;
            else 
                right--;
        }

        return area;
    }
}

Trapping the water

• 简单的思路是从左边扫一遍，记录下对于每个点最左边的最高值，和最右边的最高值,可以知道扫过的地方灌水的最大的高度即为leftmax和rightmax中较短的最高高度。然后根据这两个数组进行判断
• 思路是从左右两端分别出发，并保存左右两端的最高高度。每次loop中，比较此时左右点的高度，处理高度较小的那部分，因为只有这一部分才能确定不被另一端所影响。然后就是比较这个点的高度和这一端的最高高度，看是需要更新还是可以加入结果
• 另一个思路是用PQ

public int trap(int[] height) {
        if (height == null || height.length <= 2) return 0;

        int len = height.length;
        int ans = 0;
        for (int i = 0; i < len; i++) {
            int leftMax = 0, rightMax = 0; 
            //find left most 
            for (int j = 0; j <= i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }

            for (int j = i+1; j < len; j++)
                rightMax = Math.max(rightMax, height[j]);

            int h = Math.min(leftMax, rightMax);
            if (h > height[i])
                ans += h - height[i];

        }
        return ans;
    }

// use two pointers to make it O(n)
public int trapRainWater(int[] heights) {
        // write your code here
        int left = 0, right = heights.length - 1; 
        int res = 0;
        if(left >= right)
            return res;
        int leftheight = heights[left];
        int rightheight = heights[right];
        while(left < right) {
            if(leftheight < rightheight) {
                left ++;
                if(leftheight > heights[left]) {
                    res += (leftheight - heights[left]);
                } else {
                    leftheight = heights[left];
                }
            } else {
                right --;
                if(rightheight > heights[right]) {
                    res += (rightheight - heights[right]);
                } else {
                    rightheight = heights[right];
                }
            }
        }
        return res;
    }