题意概括

给定一个长度为 n 的整数数组 height，数组中的每个非负整数 height[i] 代表在坐标 (i, height[i]) 处的一条垂直线。你需要找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回这个最大容量。

容器的容量由两板中的短板和它们之间的距离决定，即：$\text{容量} = \min(\text{height}[i], \text{height}[j]) \times (j - i)$。

数据范围:

• $2 \le n \le 10^5$
• $0 \le \text{height}[i] \le 10^4$

基础知识

本题可以使用 双指针法 (Two Pointers) 在 $O(N)$ 的时间复杂度内解决。暴力枚举所有线对的 $O(N^2)$ 方法会超时。

双指针法的核心思想是：

1. 初始化：设置两个指针，l 指向数组的起始位置（第 0 条线），r 指向数组的末尾（第 n-1 条线）。这构成了我们初始的、宽度最大的容器。
2. 迭代计算：在一个循环中，只要 l < r，我们就计算当前 l 和 r 指针所构成的容器容量，并用它来更新我们记录的最大容量 ans。
3. 指针移动策略：这是算法的关键。容器的容量受限于较短的那条垂直线。假设 height[l] 是较短的那条。此时，无论我们如何向内移动右指针 r，容器的宽度 r-l 都会变小，而高度至多还是 height[l]，因此容量不可能增大。要想找到一个可能更大的容器，唯一的希望是移动短板，寻找一个可能更高的板来替换它。
   • 因此，如果 height[l] < height[r]，我们就移动左指针 l++。
   • 反之，如果 height[r] <= height[l]，我们就移动右指针 r--。
4. 终止：当 l 和 r 相遇时，我们已经考虑了所有可能的候选组合，循环结束，ans 中即为最大容量。

该算法的时间复杂度为 $O(N)$（因为 l 和 r 指针总共只会遍历数组一次），空间复杂度为 $O(1)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    int l = 0, r = n - 1;
    int ans = 0;

    while (l < r) {
        // 计算当前指针构成的容器容量，并更新最大值
        ans = max(ans, min(h[l], h[r]) * (r - l));

        // 移动指向较短线的指针
        if (h[l] < h[r]) {
            l++;
        } else {
            r--;
        }
    }

    cout << ans << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
9
1 8 6 2 5 4 8 3 7
输出:
49

样例 2:
输入:
2
1 1
输出:
1
*/