双指针-盛最多的水
给定一个长度为 n 的整数数组 array.有 n 条垂线, 第 i 条线的两个端点是 (i, 0) 和 (i, array[i]) .
找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水.
返回容器可以储存的最大水量.
1. 分析
首先, 本题中要想能盛最多的水, 就需要更宽的底, 作为容器两端的边就要更高, 更确切的说是容器两边的较矮的边更高, 容器短板更高.
换成数学语言, 也就意味着在二维坐标系中所占的矩形面积最大的, 两条垂直线的距离越远越好，两条垂直线的最短长度也要越长越好.
而面积是由底和高两部分构成.
底是数组索引的差值, 就是(j-i);
高是数组对应值中较小的值, 就是min(array[i], array[j]);
面积 = 底 * 高 = (j-i) * min(array[i], array[j])
2. 解答
首先, 通过分析我们已经知道了, 需要使用双指针, 分别代表i,j 的位置,要想底最大, 就需要位于数组的两端, 就是(0, array.length-1).
其次, 我们看下双指针如何移动是合理的. 指针移动的目的是为了寻找更高些的容器短板, 就需要选择较小的值, 移动到下一个位置.
3.代码
static Result maxArea(int[] array) {
Result result = new Result();
int start = 0;
int end = array.length - 1;
int maxArea = 0;
while (start < end) {
int tmp = (end - start) * Math.min(array[start], array[end]);
if (tmp > maxArea) {
result.start = start;
result.end = end;
maxArea = tmp;
}
if (array[start] > array[end]) {
end--;
} else {
start++;
}
}
result.area = maxArea;
return result;
}
static class Result{
int start;
int end;
int area;
}
public static void main(String[] args) {
int[] array = new int[]{2, 4, 1, 3, 5, 3, 1, };
Result result = maxArea(array);
System.out.println("i="+result.start + ",j=" + result.end +",area=" + result.area);
}4.总结
实现中, 时间复杂度是O(N), 空间复杂度是O(1);
且是利用双指针实现缩减搜索空间的思想解决问题的.
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-05-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读