题目描述

1. 盛水最多的容器(双指针)
   给定 n
   个非负整数 a1,a2,…,an
   ，表示平面上有 n
   条竖线，第 i
   条竖线的两个端点是 (i,ai)
   和 (i,0)
   。

请找出两条竖线，使得它们与 x
轴组成的容器能盛最多的水。

注意：不可以把线倾斜，并且 n≥2
。

输入格式
第一行包含整数 n
。

第二行包含 n
个非负整数。

输出格式
输出一个整数，表示容器的最大盛水量。

数据范围
1≤n≤105
,
1≤ai≤104
。

样例

输入样例：
9
1 8 6 2 5 4 8 3 7
输出样例：
49

算法

C++ 代码

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int l=1,r=n;
    int res=0;
    while(l<r)
    {
        res=max(res,min(a[l],a[r])*(r-l));
        if(a[l]<a[r])l++;
        else r--;
    }
    cout<<res;

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla