盛水最多的容器（LeetCode）_盛最多水的容器acm

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
输入示例1

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

输入示例2

输入：height = [1,1]
输出：1

对题目的理解
根据图片我们可以知道要想求出容器可以储存的最大水量，就是要求出两个数所围成的矩形的面积。
由此，我们可以采用双指针来分别代表矩形的两条边，方法如下：
1.定义一个整型变量left作为左指针；
2.定义一个整型变量right作为右指针；
3.(right-left)的值即为矩形的第三条边长；
所要求的矩形面积为左指针、右指针中较小的那个数再乘以第三条边长。
4.移动指针，求出下一个矩形的面积；
5.最后这些矩形面积的最大值即为所的容器所能容纳水的最大值。

解决代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int right=height.size()-1;//右指针指向数组末尾
        int left=0;//左指针指向数组的开头
        int ans=0;//ans为容器所能容纳水的最大值
        //当左指针的值小于右指针的值执行循环
       while(left<right)
       {	//用min()函数求出左右指针中的较小值并乘以第三条边的边长
           int area=min(height[left],height[right])*(right-left);
           //用max()函数求出将每次求出的矩形的面积与上一个矩形的面积作比较，求出其中的较大值
            ans=max(ans,area);
            //判断左右指针的值
            if(height[left]<=height[right])//如果左指针的值小于等于右指针的值
            left++;//使左指针右移
            else
            right--;//使右指针左移
       }
       //返回矩形面积的最大值
        return ans;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

总结

本题运用的是双指针法求出容器所能容纳水的最大值，其中最关键的是判断指针的移动，即

if(height[left]<=height[right])
left++;
else
right–;

那么我们该如何来理解左右指针的移动呢？
我们可以将左右指针所指向的值理解为容器的两块板，容器所能容纳水的值由最短的那一块板子来决定。
如果左板的值小于右板的值，我们就需要移动左板，要是移动右板，因为容器所能容纳水的值由最短的那一块板子来决定，所以无论如何移动右板，容器所能容纳水的值还是取决于左板，因此左板的值小于右板我们就移动左指针，右板的值小于左板我们就移动右指针，这样才能得到容器所能容纳水的最大值。