双指针-对撞指针

image.png

对撞指针 是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历

对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题

举个LeetCode上的例子：
leetCode-11
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.
Note: You may not slant the container and n is at least 2.

image.png

题⽬⼤意
给出⼀个⾮负整数数组 a1，a2，a3，…… an，每个整数标识⼀个竖⽴在坐标轴 x 位置的⼀堵⾼度为 ai
的墙，选择两堵墙，和 x 轴构成的容器可以容纳最多的⽔。
解题思路
这⼀题也是对撞指针的思路。⾸尾分别 2 个指针，每次移动以后都分别判断⻓宽的乘积是否最⼤

Example 1:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

java实现

    public static long maxArea(int[] heights){
        if(heights.length == 0){
            return 0;
        }
        long maxArea = 0L;
        int left = 0;
        int right = heights.length-1;
        while(left < right){
            long area = 0;
            if(heights[left]<=heights[right]){
                area = (right-left) * heights[left];
                left ++;
            }else{
                area = (right-left) * heights[right];
                right--;
            }
            maxArea = area > maxArea ? area : maxArea;

        }
        return maxArea;
    }

再举一个例子
LeetCode 881
救生艇问题
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
例子：
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

java实现

private static int countBoats(int[] people, int limit){
        people = quickSort(people);
        int count = 0;
        int left = 0;
        int right = people.length-1;
        while(left<=right){
            if(left == right){
                //其实这一步可以不用，因为无论这里怎么装船，下一步都会跳出循环了
                left++;
            }else if(people[left]+people[right]>limit){
                //只装得下一个人
                right--;
            }else{
                left++;
                right--;
            }
            count++;
        }
        return count;
    }

相关题目

• LeetCode.141.环形链表
• LeetCode.026.删除数组中重复的项
• LeetCode.881.救生艇