题目描述
给定一个长度为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; }
