最多的水 （C++代码）

解题思路:

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

--------------------- 

作者：老表Pro 

来源：CSDN 

原文：https://blog.csdn.net/qq_39241986/article/details/83577857 

版权声明：本文为博主原创文章，转载请附上博文链接！

我们需要定义i和j两个指针分别指向数组的左右两端，然后两个指针向中间搜索，每移动一次算一个值和结果比较取较大的，容器装水量的算法是找出左右两个边缘中较小的那个乘以两边缘的距离，代码如下：

C++ 解法一：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            res = max(res, min(height[i], height[j]) * (j - i));
            height[i] < height[j] ? ++i : --j;
        }
        return res;
    }
};

下面这种方法是对上面的方法进行了小幅度的优化，对于相同的高度们直接移动i和j就行了，不再进行计算容量了，参见代码如下：

C++ 解法二：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            int h = min(height[i], height[j]);
            res = max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
};

--------------------- 

作者：Grandyang 

来源：博客园 

原文：https://www.cnblogs.com/grandyang/p/4455109.html

注意事项:

如果以上解法很难读懂，可以试着先不用vector，只用一个足够大的数组获取输入、并暴力地遍历任何“两条直线”所构成容器以较短边为准可容纳的水量，找到最大值。
参考代码:

#include<stdio.h>
int a[100000];
int max(int a,int b){
    // 返回a和b中较大的值
}
int min(int a,int b){
    // 返回a和b中较小的值
}
int main(){
    int i,j,n=1,res=0;
    while(~scanf("%d",a+n)) n++;
    n--;
    for(i=1;i<=n-1;i++)
        for(j=i+1;j<=n;j++)
            res=max(res,(j-i)*min(a[i],a[j]));
    printf("%d\n",res);
    return 0;
}