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;
}
相关题目
网友评论