双指针

双指针的本质是利用传递性，从 n方 降到 n,所以不包括链表的快慢指针
传递性可以表现为有序区间收缩，两边的最值等等

例题切入

右比左最大差值

• 暴力解法： 固定一个i，然后用一个j不断在右边找，毫无疑问的n方
• 优化的点： 语义是"i要找最小，j要找最大"。j最大这个没得优化，因为未知的只能遍历。但是“i最小”这里可以做文章，比如2后面是567xxx，本来要全比较，但是如果中间出来了一个1，2就没有比较的必要了，直接给1去操作。

class Solution {
    public int maximumDifference(int[] nums) {
        //语义：如果右边比自己大，一路找过去
        //如果右边比自己小，自己使命完成了，下线就完事
        int l = 0;
        int r = 1;
        int res = -1;
        while(r < nums.length){
            //往右走
            if(nums[l] < nums[r]){
                res = Math.max(res,nums[r]-nums[l]);
            }else{
                l = r;
            }
            r++;
        }
        return res;
    }
}

不要想着一步到位

如果老是想着左扭右扭，那么一定会陷入沼泽：两个指针到底动谁？从暴力来
拿谁开刀？ 很明显，找那个矮的下手

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int i = 0, j = height.length-1;
        while(i<j){
            max = Math.max(max,(j-i)*Math.min(height[i],height[j]));
            if(height[i] < height[j]){
                i++;
            }else{
                j--;
            }
        }
        return max;
    }
}

刷题

• 三数之和 固定一个i，后面两个指针根据有序性不断往中间收缩：[1,..100]，大了右边往左，小了左边往右