算法学习(3)-经典的双指针法则

双指针基本理解

1. 首先什么是双指针, 双指针其中一个为快指针一个为慢指针, 慢指针顾名思义运行或者前进的速度较慢, 为什么会这样呢一定是比快指针所需满足的条件多, 因此慢指针所指的一般是过滤完的内容.
2. 为什么要用双指针, 这里用到了典型的算法解题思维-----升维, 就是一个一维数组我把它变成二维数组(条表的实现就是一个很典型的升维思想), 那升维的目的是获得更多的信息, 双指针也是一个升维操作本质上相当于在一个数组里干了两个数组的事情(排序).
3. 双指针个人感觉会更常用在排序里如果后面发现不是再改.

双指针例题

1. 删除排序数组中的重复项

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;// 注意嘴
    int i = 0;  //慢指针
    for (int j = 1; j < nums.length; j++) {//j 为快指针
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j]; // 可以写成nums[i++]=nums[j] 先运行赋值再运行++.
        }
    }
    return i + 1;
}

• 注意这里从j=1开始是因为第一个元素必定要留下, 慢指针+1=不重复元素个数.
• i 为慢指针, j 为快指针, i 指向目前不重复元素的最后一位, j指向当前数组元素.
  i在这里的话[1,2,3,5,5,5,5,2,3]指向的是3或者5取决于j在哪, j在第一个5的话i为3.
• 如果目前j指针所指数组元素不等于非重复元素的最后一位的话, 那么把慢指针加1并且把快指针所指的元素赋给慢指针所在元素, 注意在慢指针+1的这一步时慢指针是没有意义的它指向的不过是平平无奇的一个数组元素, 但是当快指针指的值回来的时候就有了原来的意义.
• 快指针和慢指针在没有出现重复的时候是一直相等的, 当出现重复快指针就会变快, 慢指针就会停留在最后一个非重复数那里被拉开(这也是我们说的过滤条件决定的). 重要的是慢指针和快指针的差距是不会缩减的(本题是这样)这也侧面说明了我们只管了前面的排序.
• 这道题相对其他双指针简单也为没有处理剩下的部分只是放着不动了.
  
  图片来此leetcode-Max.

2. 移动零

这个利用前面的思想慢指针定义为最后一个不为零的元素, 快指针定义为for循环中的控制,
那么差别在哪呢, 差别在于刚刚那个慢指针+1=快指针这一步覆盖掉了原来数组中的元素, 但由于是重复的我们没去管, 但这里不一样了这里要把覆盖掉的0放到最后比刚刚难点. 当然如果想搞个笨一点的用for循环把上一题的给抄了然后后面自己给for循环赋成0. 复杂度一样.

class Solution {
	public void moveZeroes(int[] nums) {
		if(nums==null) {
			return;
		}
		int j = 0;
		for(int i=0;i<nums.length;++i) {
			if(nums[i]!=0) {
				nums[j] = nums[i];
                if(j!=i){
                    nums[i]=0;
                }
                j++;
			}
		}
		
	}
}

上述代码是实现了整体的操作, 而下面是处理后半部分不用循环的精华.

if(j!=i){
                    nums[i]=0;
                }
                j++;

这个代码片段的意思是如果慢指针不等于快指针, 为什么不等上面说过了因为过滤条件的原因导致慢指针拉下了如果不处理就会一直拉下也无法不用循环实现零的补充, 而这里这个意思就是在快指针所指元素不等于零且快指针不等于慢指针的时候(注意这时候已经完成了非零元素的移动啦) 将无用的快指针下元素(之前我们是扔着不管的) 赋值成零, 这样就完成了交换啦, 那为什么等于零的时候不处理呢, 你想一下把不等于零的往前挪, 等于零的不就相当于往后挪了嘛, 这和我们刚才讲的把快指针下的无用元素赋值成零的想法十分一致.

3. 盛最多的水

先来个暴力法(最垃圾的算法-我最开始想到的)

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

时间复杂度O(n(n-1)/2)也就是n²级别的时间复杂度.

之后看了leetCode的解题思路看到了双指针.
这里的双指针和上面讲的快慢指针不同了, 上面之所以有快慢指针之分是因为有两个过滤条件, 而这里只有一个条件就是短的那个向前移(期盼有比它高的出现只有这样才可能有更大的容量)

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

1. 这里面的l指针指向最左边, r指针指向最右边(最开始的时候)
2. 每一轮只计算两个指针与x轴所围成的容量, 因为在不动指针的情况下这就是最大值, 比如不用r而用r前面的那一根(假设r是高的那个), 那么对于新的容量来说容量一定比之前小, 因为低的高度没变长度变短了.
3. 理解了上面的话, 其实就很简单了, 唯一一种可能比目前容量大的方式是, 移动低的指针, 因为一旦低的边改变了很有可能高度就会变高(变高的上限为刚刚没动的最高的边), 这时候我们至少有希望获得比原来更高的容量, 这就是双指针法的精髓.
   
   上图中3这个边不动你就不可能获得比37这个组合更大容量的容器.
   但如果你懂了比如变成8了, 那高度的增益有可能会超越长度下降.

核心思想: 只要最低边不变高容量就永远不会变大(因为长度最开始定义的最大之后肯定减小).