基础算法 - 双指针
双指针（Two Pointers）是一种常见的算法技巧，通常用于解决数组或链表中的问题。它的核心思想是使用两个指针在给定条件下同时移动，以解决问题或优化算法性能。
主要特点
- 并行移动：双指针通常会从数组或链表的两端开始，并以不同的速度向中间移动，直到两个指针相遇或交叉。
- 降低时间复杂度：通过使用双指针，可以在不增加空间复杂度的情况下，降低问题的时间复杂度，通常优于暴力求解方法。
- 适用场景：适合解决排序数组的查找问题、链表中的环检测、数组或字符串的滑动窗口问题等。
相关题目
难度：简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public void moveZeroes(int[] nums) {
int len = nums.length;
int nonZero = 0;
for (int i = 0; i < len; i++) {
if (nums[i] != 0) {
nums[nonZero++] = nums[i];
}
}
while (nonZero < len) {
nums[nonZero++] = 0;
}
}
}
|
难度：中等
暴力解法：
这是最朴素的暴力解法，计算出每一个可能的结果然后进行比较，当然是一定会超时的，时间复杂度为n^2^。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int maxArea(int[] height){
int res = Integer.MIN_VALUE;
int len = height.length;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
int w = j - i;
int h = Math.min(height[i],height[j]);
res = Math.max(h*w,res);
}
}
return res;
}
}
|
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int maxArea(int[] height){
int res = Integer.MIN_VALUE;
int left = 0;
int right = height.length-1;
while(left<right) {
int w = right - left;
if (height[left] < height[right])
res = Math.max(res, height[left++] * w);
else
res = Math.max(res, height[right--] * w);
}
return res;
}
}
|
与暴力解法相比，双指针解法没有计算那些根本没有意义的面积（比如说哪些让更高的一端收缩的面积），双指针更关注于可能得更大值。
如果要暴力破解的话，时间复杂度应该为n^3^，而且还要去重的操作，非常繁琐，肯定会超时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int len = nums.length;
int cur = Integer.MAX_VALUE;
for (int i = 0; i < len - 2; i++) {
if (cur == nums[i]) continue;
cur = nums[i];
if (cur > 0) break;
int head = i + 1;
int tail = len - 1;
while (head < tail) {
if (cur + nums[head] + nums[tail] == 0) {
List<Integer> tmp = new ArrayList<>();
tmp.add(cur);
tmp.add(nums[head]);
tmp.add(nums[tail]);
res.add(new ArrayList<>(tmp));
while (head < tail && nums[head] == nums[head + 1])
head++;
while (head < tail && nums[tail] == nums[tail - 1])
tail--;
head++;
tail--;
} else if (cur + nums[head] + nums[tail] < 0) {
head++;
} else {
tail--;
}
}
}
return res;
}
}
|
方法1 - 按行求
利用雨水一定在凹槽里的特点 ，又根据层数计算雨水，将多层分解为多个单层，单层的逻辑很简单。
这样的时间复杂度为 n*(max(height))
如果max(height)很大，那么很容易超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public int trap(int[] height) {
int sum = 0;
int max = getMax(height);
for (int i = 1; i <= max; i++) {
boolean isStart = false;
int temp_sum = 0;
for (int j = 0; j < height.length; j++) {
if (isStart && height[j] < i) {
temp_sum++;
}
if (height[j] >= i) {
sum = sum + temp_sum;
temp_sum = 0;
isStart = true;
}
}
}
return sum;
}
private int getMax(int[] height) {
int max = 0;
for (int i = 0; i < height.length; i++) {
if (height[i] > max) {
max = height[i];
}
}
return max;
}
作者：windliang
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
方法2 - 按列求
按列求是比较容易想到的方法。
关键思路：如果要求某一列的雨水，需要考虑哪些呢？ – > 左边最高的墙、右边最高的墙、该列的墙的高度，雨水为 = max(min(left,right) - cur,0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int trap(int[] height) {
int res = 0;
int len = height.length;
for(int i=1;i<len-1;i++){
int cur = height[i];
int leftMax = 0;
int rightMax = 0;
for(int l=i-1;l>=0;l--)
leftMax = Math.max(leftMax,height[l]);
for(int r=i+1;r<len;r++)
rightMax = Math.max(rightMax,height[r]);
int low = Math.min(leftMax,rightMax);
res+=Math.max(low-cur,0);
}
return res;
}
}
|
这个思路简单，代码简洁，但是时间复杂度稍高n^2^
因为对于每一列，我们都需要重新向左向右遍历最大值。
方法3 - DP
在上一个方法中，我们求leftMax和rightMax的时候很多元素被重复遍历了很多次，造成了时间复杂度稍高。
那么我们就可以使用记忆化搜索的方法来优化求leftMax和rightMax，也就是使用动态规划的方法优化（空间换时间）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int trap(int[] height){
int res = 0;
int len = height.length;
int[] leftMax = new int[len];
int[] rightMax = new int[len];
for(int i=1;i<len-1;i++){
leftMax[i] = Math.max(leftMax[i-1],height[i-1]);
int k = len-1-i;
rightMax[k] = Math.max(rightMax[k+1],height[k+1]);
}
for(int i=1;i<len-1;i++){
int cur = height[i];
int low = Math.min(leftMax[i],rightMax[i]);
res+=Math.max(low-cur,0);
}
return res;
}
}
|
注意，求rightMax[]的时候需要反着来。
这下子时间复杂度为O(n)，但是空间复杂度上去了。
方法4 - 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int trap_redo(int[] height){
int res = 0;
int left = 1;
int right = height.length-2;
int leftMax = height[left-1];
int rightMax = height[right+1];
while(left<=right){
if(leftMax<rightMax){
res+=Math.max(leftMax-height[left],0);
leftMax = Math.max(leftMax,height[left]);
left++;
}else{
res += Math.max(rightMax-height[right],0);
rightMax = Math.max(rightMax,height[right]);
right--;
}
}
return res;
}
|
因为我们要的出某一列的水，就要知道该列左右各两边最高的之中的最低的一个有多低，但并不关心更高的哪一个有多高，所以，只要当右边有一个比左边最高的还高的时候就可以计算当前列的水了，让left在左边，right在右边，两个指针分别往中间靠，边靠边更新leftMax和rightMax，哪边比较小，就计算那边所对应的列，同时将对应的指针改变。
