AcWing 1575. 盛水最多的容器

题目

给定 个非负整数 ，表示平面上有 条竖线，第 条竖线的两个端点是 和 。

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

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

输入格式

第一行包含整数 。

第二行包含 个非负整数。

输出格式

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

数据范围

,
。

输入样例：

9
1 8 6 2 5 4 8 3 7

输出样例：

49

题解

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int h[N];
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++ i) scanf("%d", &h[i]);

    // 双指针的做法，两指针做高度比较，小的指针往中间移动
    int res = 0;
    for (int i = 0, j = n - 1; i < j;)
    {
        res = max(res, (j - i) * min(h[i], h[j]));
        if (h[i] > h[j]) -- j;
        else ++ i;
    }

    cout << res << endl;

    return 0;
}