Graphic LeetCode -- 11. Containers of most water (difficulty: medium)

一、题目

给定一个长度为 n 的整数数组 height .有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) .

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水,返回容器可以储存的最大水量.

说明：你不能倾斜容器.

二、示例

2.1> 示例 1：

【输入】[1,8,6,2,5,4,8,3,7]
【输出】49
【解释】图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7].在此情况下,容器能够容纳水（表示为蓝色部分）的最大值为 49.

2.2> 示例 2：

【输入】height = [1,1]
【输出】1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

三、解题思路

3.1> 思路1：双向指针

通过题意,We will receive an array of integersheight,它里面有n个数值,represents the height of the stake.Any two stakes can be combined withx轴Composed of a container to sink,So which combination sink can hold more water?？In fact, there are two factors in this question that are the key points of the water capacity：one is a sinkx轴的长度,The other is the height of the shortest stake of the two stakes.The product of these two values ​​is the size of the water holding capacity..

Then the solution to the two-way pointer is to create two pointers——head头指针和tail尾指针.最初head指向height数组中index=0的位置,tail指向height数组中index=height-1的位置.So at this time, suppose we are as shown in the following figure,height[head]是小于height[tail]的,head指针与tailThe length of the pointer isx（即：tail - head = height - 1 - 0）,Then the water capacity that the sink can carry at this time is equal to：height[head] * x.如下图所示：

Then according to the double pointer arithmetic,我们需要让head指针或者tailpointers move towards each other,So which pointer to move？We will compare the heights of the two stakes according to,to move the shorter one.比如,headThe stake pointed to by the pointer is shorter,那么我们将head指针向右移动.但是如果是tailThe stake pointed to by the pointer is shorter,那么我们就将tail指针向左移动.When two Pointers met in one location,则结束整个过程.

那么有同学会问,Why make such a comparison?？这道题,我们一般来说,The first reaction should be two layersfor循环,即,To lock the first wooden stakes,Then go to compare other stakes in turn,capacity per calculation,通过Math的max函数,Only record the maximum capacity.Then we lock the second stake,Compare with other stakes（not the first stake）,然后一次类推.This way is right,But it belongs to the category of brute force.那么,Can a two-way pointer guarantee the correctness of the calculation?？

Let's take the above picture as an example,由于最初的headThe height of the pointed stake isheight[0],tailThe height of the pointed stake isheight[height.length - 1],他们之间的距离为x,由于height[0] 小于 height[height.length - 1],So the water capacity of the container is height[0] * x,这里的xalready at the maximum,也就是说,无论head指针和tailhow the pointer moves,The distance between the two pointers will not be greater thanx.Then we actually相当于“锁定”max container bottomx了,And every time you movehead指针还是tail指针,for the bottom of the containerx的影响,are always decreasing,Then its change is a constant decreasing trend.And in terms of container height,indeed a change,Because we don't know whatheadpointed stake high,还是tailpointed stake high.

那么此时,Our second question is,How to move the stake？Why move the shorter one?？By the above formula we getheight[head] * x（前提是headThe height of the stake is less thantailstake height）,那么假设我们Move higher stakes——即tail指针,Then the bottom of the container is：x - 1,Since the shorter stakes are not movedheight[head],所以无论tailWhat is the height of the stake pointed to by the pointer?,The total capacity height will not exceedheight[head]的高度,Then the maximum possible capacity is：height[head] * (x - 1);Then if weMove lower stakes——即head指针,Then the bottom of the container is：x - 1,Since the higher stakes are not movedheight[tail],所以无论headWhat is the height of the stake pointed to by the pointer?,The total capacity height will not exceedheight[tail]的高度,Then the maximum possible capacity is：height[tail] * (x - 1);那么由于head < tail,So naturallyheight[head] * (x - 1) <height[tail] * (x - 1)的结论.And this question is to get the maximum water capacity,所以,Nature is about to move to a stake with shorter.具体如下图所示：

Then we have introduced how to calculate the maximum water holding capacity above.,The following is the first example in the title1为例,Graphical way of performing through each step,Completely show the whole process of one execution.那么示例1中,height数组中的元素为[1,8,6,2,5,4,8,3,7],We in turn move throughhead指针或者tail指针,and calculate each“最大容量” ,并通过Math的max函数,Return the final maximum capacity as the result.下面是具体的8个执行步骤,如下所示：

四、代码实现

4.1> 实现1：双向指针

class Solution {
    public int maxArea(int[] height) {
        int result = 0, head = 0, tail = height.length - 1;
        while(head < tail) {
            if (height[head] <= height[tail]) {
                result = Math.max(height[head] * (tail - head), result);
                head++;
            } else {
                result = Math.max(height[tail] * (tail - head), result);
                tail--;
            }
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 .

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ (^o^)/ ~ 「干货分享,每天更新」

往期推荐

题目来源：力扣（LeetCode）