算法练习——盛最多水的容器

2021年1月12日LeetCode每日一题为1203. 项目管理,又是一道图结构的算法,叫做拓扑排序,直接就是一脸懵逼,只能选择另一道11. 盛最多水的容器来练习了,这道题也是可以使用递归的方式来做的,我们将所有情况能装的水的数量求出来取最大值即可,从下标begin到下标end,max返回这次计算的水的结果,很明显这样的递归是会超出时间限制的。代码如下:

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 max = 0;
for (int i = 0; i < height.length; i++) {
max = Math.max(max, max(height, i, height.length - 1));
}
return max;
}

public static int max(int[] height, int begin, int end) {
if (begin == end) return 0;
int min = Math.min(height[begin], height[end]);
int m = max(height, begin, end - 1);
int water = min * (end - begin);
return Math.max(water, m);
}
}

仔细想想,好像没什么必要将所有可能都计算出来,因为我们只要找到距离最远的两个比较大的就可以了,因此采用双指针来找距离比较远,数字又比较大的,比较左右两个指针指向的数字,指向较小的数字指针向中间靠,最终两个指针相碰时结束,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int max = 0;
while (left < right) {
int min = Math.min(height[left], height[right]);
max = Math.max(max, min * (right - left));
if (min == height[left]) {
left++;
} else {
right--;
}
}
return max;
}
}

虽然这题没有必要使用递归,但是可以使用递归来解决的。今天又一次出现了图结构的算法,可见树和图的算法的重要性,不难发现难度为困难的算法基本上都是树与图相关的。好好加油,不管多累也要坚持下去!