题目描述

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

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

​ 输出容器可以储存的最大水量。

**说明：**你不能倾斜容器。

输入格式

输入共 2行。

输入的第一行为一个正整数 n，表示n条垂线。

输入的第二行为n个正整数，第i个数代表a[i]的值。

输出格式

输出一行一个整数，表示容器可以储存的最大水量。

输入输出样例

输入 #1复制

9
1 8 6 2 5 4 8 3 7

输出 #1复制

49

输入 #2复制

2
1 1

输出 #2复制

1

说明/提示

对于 100% 的数据，2≤n≤10^6,0≤a[i]≤10^4。

思路：

我们可以分别让变量l和r作为数组开头和结尾的位置，开一个while循环，通过比较l和r位置的高低，用低的来进行容积计算（（r-l）*h），如何谁低，谁位置就进行位移，比如l位置低，l++，这样才能找到更高的位置进行计算，当l和r重合的时候也就是所有容积都计算了的时候，时间复杂度o（n）。

主播的代码（主播在编译器上写的，不是力扣平台）:

#include <iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<string>
#include<math.h>
#include <iomanip>
#include<unordered_map>
#include <unordered_set>
#include<array>
#define gets(S) fgets(S,sizeof(S),stdin)
#define ll long long
const ll N = 2e6 + 5;
const ll Max = 0x3f3f3f3f;
using namespace std;

ll n;

int main() {
	cin >> n;

	vector<ll>saki(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> saki[i];
	}

	ll l = 1, r = n, sum = 0;
	while (l < r) {
		ll w = min(saki[l], saki[r]);
		sum = max(((r - l) * w), sum);
		saki[l] >= saki[r] ? r-- : l++;
	}
	cout << sum;

	return 0;
}