你好！我是你的OI教练。LeetCode11 “盛最多水的容器”，是一道非常经典的双指针（Two Pointers）与贪心策略结合的入门题。

---

第一部分：NOI风格题目描述

题目名称：盛水容器 (Water Container)

【题目描述】 给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。 在平面直角坐标系中，对于每个 $i$ ($1 \le i \le n$)，存在一条垂直线段，其两个端点分别为 $(i, 0)$ 和 $(i, a_i)$。 你需要从这 $n$ 条线段中找出两条线段（记下标为 $i$ 和 $j$，且 $i < j$），这两条线段与 $x$ 轴共同构成一个容器。 容器的盛水量由“短板效应”决定，即两条线段中较短的那条的高度乘以它们在 $x$ 轴上的距离。 请你计算该容器最多能容纳多少水。

【输入格式】 输入共两行。 第一行包含一个整数 $n$，表示线段的数量。 第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，分别表示每条线段的高度，整数之间用空格分隔。

【输出格式】 输出一个整数，表示容器能容纳的最大水量。

【样例输入】

9
1 8 6 2 5 4 8 3 7

【样例输出】

49

【样例解释】 选择下标为 2（高度为 8）和下标为 9（高度为 7）的两条线段。 距离为 $9 - 2 = 7$。 高度由较短的一边决定，即 $\min(8, 7) = 7$。 最大水量为 $7 \times 7 = 49$。

【数据范围与提示】

• 对于 $30\%$ 的数据，满足 $n \le 1000$。
• 对于 $100\%$ 的数据，满足 $2 \le n \le 10^5$，$0 \le a_i \le 10^4$。
• 请注意时间复杂度，$O(n^2)$ 的算法可能会超时。

---

第二部分：预备知识点总结

在解决这道题之前，你需要掌握以下知识：

1. 数组的基本操作：下标访问，简单的遍历。
2. 双指针算法（Two Pointers）：特别是对撞指针（左右指针向中间移动）的写法。
3. 贪心思想（Greedy）：在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
4. 简单的几何面积计算：矩形面积 = 底 $\times$ 高。

---

第三部分：启发式教学引导（草稿纸推演）

同学们，拿起你们的草稿纸和笔，我们不直接写代码，先画图来模拟一下这个过程。

1. 朴素思路（暴力枚举）

• 提问：最笨的办法是什么？
• 草稿：是不是可以把所有可能的 $(i, j)$ 对都算一遍？
  • $i=1$, $j=2 \dots n$
  • $i=2$, $j=3 \dots n$
  • ...
• 分析：这需要两层循环。
• 复杂度：时间复杂度是 $O(n^2)$。看一眼数据范围 $n=10^5$，计算机一秒大概跑 $10^8$ 次运算，$10^{10}$ 肯定会TLE (Time Limit Exceeded)。我们需要更快的算法，最好是 $O(n)$。

2. 观察公式与寻找规律

• 公式：$Area = (j - i) \times \min(a_i, a_j)$。
• 核心矛盾：我们想要**底（宽度）越宽越好，同时高（短板）**越高越好。

3. 双指针推演（关键一步！）

画一个横轴，标上 $1$ 到 $n$。假设我们有两个指针，一个在最左边 $L=1$，一个在最右边 $R=n$。

• 当前状态：宽度是最大的 $(n-1)$。
• 决策：我们要把 $L$ 向右移，还是把 $R$ 向左移？

让我们在草稿纸上画两个柱子：

• $L$ 柱子高度是 3。
• $R$ 柱子高度是 8。
• 当前水位高度取决于谁？取决于 $L$（高度3）。

思考实验 1：如果一定要移动高的一边（也就是 $R$ 左移到 $R-1$）：

• 宽度：变小了。
• 高度：
  • 如果新柱子 $R-1$ 很高（比如100），水位高度还是受限于 $L$（高度3）。
  • 如果新柱子 $R-1$ 很矮（比如1），水位高度变成了 1。
• 结论：宽度一定变小，高度要么不变，要么变小。
• 推论：移动高的一边，面积一定变小。这步操作是废的，不可能产生最大值。

思考实验 2：如果移动矮的一边（也就是 $L$ 右移到 $L+1$）：

• 宽度：变小了。
• 高度：
  • 如果新柱子 $L+1$ 很高（比如10），水位高度可能就被 $R$ 或者 $L+1$ 决定，可能变成 8。
  • 虽然宽度小了，但高度可能大幅增加。
• 结论：移动矮的一边，虽然牺牲了宽度，但保留了高度变大的可能性，从而面积可能变大。

4. 算法流程总结

1. 定义 left = 1, right = n。
2. 计算当前面积，更新最大值 ans。
3. 贪心策略：比较 height[left] 和 height[right]：
   • 如果你是矮的那一边，你就是瓶颈，你不动，面积永远上不去。所以矮的那个指针向内移动。
   • 如果是平局，任意移动一边（或者两边都移）均可（数学上可以证明）。
4. 重复直到 left == right。

5. 复杂度分析

• 时间复杂度：两个指针一共走了 $n$ 步，每个元素只被访问一次。$O(n)$。完美解决 $10^5$ 的数据。
• 空间复杂度：只需要存几个变量，$O(1)$。

---

第四部分：读题关键词与坑点

在考场上读这类题，请圈出以下关键词：

1. “垂直线段”、“x轴”、“容器” $\rightarrow$ 这是一个几何背景的题目，将其抽象化为数组模型。
2. “盛水量”、“短板” $\rightarrow$ 暗示了 $\min(a_i, a_j)$ 这个条件，这是解题的核心约束。
3. “最多”、“最大” $\rightarrow$ 优化目标。
4. 数据范围 $10^5$ $\rightarrow$ 这是一个强烈的信号，拒绝 $O(n^2)$，提示使用 $O(n)$ 或 $O(n \log n)$ 的算法。

常见坑点：

• 下标问题：题目通常是 $1$ 到 $n$，C++数组是 $0$ 到 $n-1$，注意转换。
• 数据类型：虽然 $10^4 \times 10^5 = 10^9$ 在 int 范围内，但如果数据范围稍大（例如 $h \le 10^9$），则必须使用 long long。养成好习惯，涉及面积、乘积，优先考虑 long long。

---

第五部分：NOI风格参考代码 (C++14)

/**
 * NOI Style Solution
 * Problem: Container With Most Water
 * Algorithm: Two Pointers / Greedy
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */

#include <iostream>
#include <vector>
#include <algorithm> // for std::max, std::min

using namespace std;

// 建议使用 fast I/O，虽然本题数据量读入压力不算极大，但这是好习惯
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;
int a[MAXN]; // 静态数组往往比 vector 稍微快一点点，且不用担心动态扩容

int main() {
    fast_io();

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 双指针初始化
    // L 指向数组头部 (下标 0)
    // R 指向数组尾部 (下标 n-1)
    int L = 0;
    int R = n - 1;
    
    // 使用 long long 防止潜在的溢出（虽然本题数据 int 够用，但在 NOI 中要谨慎）
    long long max_area = 0;

    while (L < R) {
        // 计算当前宽度
        int width = R - L;
        
        // 计算当前高度：受限于较短的那一块木板
        // 这里 h 为当前容器的有效高度
        int h = min(a[L], a[R]);
        
        // 更新最大面积
        long long current_area = (long long)width * h;
        max_area = max(max_area, current_area);

        // 贪心决策：哪边短，哪边就向内移动
        // 因为移动长边，宽度减小，高度不可能增加（受限于未移动的短边），面积一定减小
        // 只有移动短边，才有可能在损失宽度的情况下，找到更高的板子来弥补
        if (a[L] < a[R]) {
            L++;
        } else {
            R--;
        }
    }

    cout << max_area << endl;

    return 0;
}