力扣 11.盛最多水的容器 简单的双指针算法 题解

题目描述

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