对撞型,灌水类
双指针算法普遍分为三种
对撞类
two sum 类,partition 类
窗口类
并行型
掌握 3-way partition 和 k-way partition.
对撞型指针的本质是,不需要扫描多余的状态。在两边指针的判断之后,可以直接跳过其中一个指针与所有另外一面 index 组成的 pair.
这道题如果暴力搜索的话,需要考虑的 pair 个数显然是 O(n^2). 但是用对撞型指针,可以有效跳过/剪枝不合理的 pair 组合。
排序之后的数组具有了单调性,两根指针的移动就代表了“增加”和“减少”。这种单调性保证了一条重要性质:
如果 nums[i] + nums[j] > target,那么 nums[i ~ j-1] + nums[j] > target.
因此 i,j 指向的不仅仅是元素,也代表了利用单调性,i,j 之间所有的 pair.
public class Solution {
/**
* @param nums: an array of integer
* @param target: an integer
* @return: an integer
*/
public int twoSum2(int[] nums, int target) {
// Write your code here
if(nums == null || nums.length == 0) return 0;
Arrays.sort(nums);
int count = 0;
int left = 0;
int right = nums.length - 1;
while(left < right){
if(nums[left] + nums[right] <= target){
left ++;
} else {
count += right - left;
right --;
}
}
return count;
}
}
总的思路对了,但是一开始的做法掉到了坑里,就是用 i = 1 to n 做最外循环,j 和 k 都在 i 后面。
这种思路的问题是,想 num[i] + num[j] > num[k]的话,如果当前条件不满足,j++ 和 k-- 都可以是对的。就违反了双指针不同程度上利用的单调性,一次只把一个指针往一个方向推,而且不回头。
所以顺着这个问题想,如果我们最外围遍历的是 k,而 i, j 都处于 k 的左面,那么每次就只有一个正确方向,挪动一个指针可以保证正确性了,即让 num[i] + num[j] 变大,或者变小。
public class Solution {
/**
* @param S: A list of integers
* @return: An integer
*/
public int triangleCount(int S[]) {
// write your code here
Arrays.sort(S);
int count = 0;
for(int k = 0; k < S.length; k++){
int i = 0;
int j = k - 1;
while(i < j){
if(S[i] + S[j] <= S[k]){
i ++;
} else {
count += j - i;
j --;
}
}
}
return count;
}
}
这种“灌水”类问题和双指针脱不开关系,都要根据木桶原理维护边界;在矩阵中是外围的一圈高度,在数组中就是左右两边的高度。
因为最低木板的高度决定水位,高位的木板有着另一种单调性,即高位木板向里移动的所有位置,形成的 container 水量都小于原来位置。
public class Solution {
/**
* @param heights: an array of integers
* @return: an integer
*/
public int maxArea(int[] heights) {
// write your code here
if(heights == null || heights.length == 0) return 0;
int max = 0;
int left = 0;
int right = heights.length - 1;
while(left < right){
int width = right - left;
int curArea = Math.min(heights[left], heights[right]) * width;
max = Math.max(max, curArea);
if(heights[left] < heights[right]){
left ++;
} else {
right --;
}
}
return max;
}
}
Trapping Rain Water
木桶原理的算法版,最两边的板子形成一个木桶,由两块板子最低的那块决定水位。每次都从两边最低的方向向里扫描。
因为 i,j 当前高度未必是当前左右两边最高高度,每次更新的时候要注意维护下。
public class Solution {
public int trap(int[] height) {
if(height == null || height.length <= 2) return 0;
int trapped = 0;
int i = 0;
int j = height.length - 1;
int leftMax = height[i];
int rightMax = height[j];
while(i < j){
if(leftMax < rightMax){
if(i + 1 < height.length && height[i + 1] < leftMax){
trapped += leftMax - height[i + 1];
}
i++;
leftMax = Math.max(leftMax, height[i]);
} else {
if(j - 1 >= 0 && height[j - 1] < rightMax){
trapped += rightMax - height[j - 1];
}
j--;
rightMax = Math.max(rightMax, height[j]);
}
}
return trapped;
}
}
Last updated
Was this helpful?