题目描述
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。
输入描述:
第一行一个整数N，表示数组长度。
接下来一行N个数表示数组内的数。
输出描述:
输出一个整数表示能装多少水。

输入
6
3 1 2 5 2 4
输出
复制
5

思路：
对于L位置，其水平线为min{左数最大值，右侧最大值}

方法1
初始想法：先找到最高点，对于左右两边，分别依次找次高点，直到次高点为边界，每次加上次高点中间的水量（简单的说，就是从最高点向两边找“坑”)

#include<iostream>
#include<vector>
using namespace std;
#define LENGTH 1000001

int arr[LENGTH];
int getMaxID(int l, int r)
{
    int max = arr[l];
    int maxID = l;
    for (int i = l+1; i < r; ++i)
    {
        if (max < arr[i])
        {
            max = arr[i];
            maxID = i;
        }
    }
    return maxID;
}
long long getLSum(int l, int r)
{
    long long sum = 0;
    for (int i = l+1; i < r; ++i)
    {
        sum += arr[l] - arr[i];
    }
    return sum;
}
long long getRSum(int l, int r)
{
    long long sum = 0;
    for (int i = l; i < r; ++i)
    {
        sum += arr[r] - arr[i];
    }
    return sum;
}

int main()
{
    int N;
    cin >> N;
    long long sum = 0;
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
    }
    int maxID = getMaxID(0, N);        
    int p = maxID;//左标
    int q = maxID;//右表
    while (p != 0)
    {
        int p1 = getMaxID(0, p);
        sum += getLSum(p1, p);
        p = p1;
    }
    while (q != N-1)
    {
        int q1 = getMaxID(q+1, N);
        sum += getRSum(q+1, q1);
        q = q1;
    }
    cout << sum;
}

想法比较朴素，超时，通过90%
方法2
参考网络上的想法：由于对每个点来说，水平线都为左数组最大值和右数组最大值中较小的那个值，可以通过辅助数组记录每个点左右数组最高值，时间复杂度为O(N)。

int main()
{
    int N;
    cin >> N;
    long long sum = 0;
    vector<int> arr(N), l(N, 0), r(N, 0);
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
    }
    for (int i = 0; i<N - 1; ++i)
    {
        l[i + 1] = arr[i]>l[i] ? arr[i] : l[i];
        r[N - i - 2] = arr[N - i - 1] > r[N - i - 1] ? arr[N - i - 1] : r[N - i - 1];
    }
    for (int i = 0; i < N; ++i)
    {
        if (arr[i]>l[i] || arr[i] > r[i]) continue;
        else if (l[i] > r[i]) sum += r[i]-arr[i];
        else sum += l[i]-arr[i];
    }
    cout << sum;
}

很好理解，并且顺利通过
方法三：
方法二中，两个辅助数组都是递推的，可以边遍历，边生成两个辅助值。
设置两个指针L和R，初始分别指向arr[1]和arr[arr.length-2]位置，指定两个变量leftMax和rightMax，初始分别为arr[0]和arr[arr.length - 1]，leftMax表示[0…L-1]位置中的最大值，rightMax代表[R+1…arr.length-1]位置上的最大值。
根据leftMax与rightMax大小进行指针移动，进行遍历，可减小空间复杂度。
方法四：
XWFLS大佬的方法。直接建立水平线，每次更新，精妙极了，如下：

int main()
{
    int N;
    cin >> N;
    long long sum = 0;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
    }
    auto l = arr.begin();//左指针
    auto r = --arr.end();//右指针
    int lower = 0;
    int level = 0;
    while (l < r)
    {
        lower = *l < *r ? *l++ : *r--;
        level = level>lower ? level : lower;
        sum += level - lower;
    }
    cout << sum << endl;
}

核心代码就三行，太精致了！！！