双指针-盛最多的水

一个架构师

发布于 2022-06-27 15:20:54

2770

发布于 2022-06-27 15:20:54

文章被收录于专栏：从码农的全世界路过

给定一个长度为 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 删除

容器