1.纯暴力（TLE）
2.优化纯暴力（多用两个数组空间）
3.双指针算法（不需要额外空间）

方法一：纯暴力（TLE）

#include<iostream>

using namespace std;
const int N = 1e5+10;
int h[N];
int main()
{
    //纯暴力解法，会TLE
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> h[i];

    int ans = 0;
    for(int i=0; i<n; i++)
    {
        //计算i左边的最大值，即：[0,i-1]
        int lmax = -1;
        for(int j=0;j<=i-1;j++)
            lmax = max(lmax, h[j]);

        //计算i右边的最大值，即：[i+1,n-1]
        int rmax = -1;
        for(int j=i+1;j<=n-1;j++)
            rmax = max(rmax, h[j]);

        //计算当前位置i能存的水量并累加到ans上
        ans += max(min(lmax, rmax)-h[i], 0);

    }

    cout << ans << endl;
    return 0;
}

方法二：优化纯暴力（多用两个数组空间）

#include<iostream>

using namespace std;
const int N = 1e5+10;
int h[N], l_max[N], r_max[N];
int main()
{
    //优化纯暴力解法，l_max[N]和r_max[N]一次性准备好，
    //不用反复计算，但多用了两个数组的空间
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> h[i];

    //数据预处理，准备l_max和r_max数组，
    //本次用的左闭右开区间[ ) ，有点不好想；
    //用左闭右闭区间[ ] ，也可以且好想一点。

    //l_max[i]表示[0,i)的最大值
    l_max[0] = h[0];
    for(int i=1;i<n;i++)
        l_max[i] = max(l_max[i-1], h[i-1]);

    //r_max[i]表示(i,n-1]的最大值
    r_max[n-1] = h[n-1];
    for(int i=n-2;i>=0;i--)
        r_max[i] = max(r_max[i+1], h[i+1]);

    int ans = 0;
    for(int i=0; i<n; i++)
    {
        //计算当前位置i能存的水量并累加到ans上
        ans += max(min(l_max[i], r_max[i])-h[i], 0);
    }

    cout << ans << endl;
    return 0;
}

方法三：双指针算法（不需要额外空间）

#include<iostream>

using namespace std;
const int N = 1e5+10;
int h[N];
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> h[i];

    int l=1, r=n-2;
    //lmax表示 [0, l) 的最大值，左侧最大值
    //rmax表示 (r, n-1] 的最大值，右侧最大值
    int lmax = h[0], rmax = h[n-1];
    int ans = 0;
    while(l<=r)
    {
        if(lmax <= rmax)
        {
            ans += max(0, lmax-h[l]);
            lmax = max(lmax, h[l]);
            l++;
        }
        else
        {
            ans += max(0, rmax-h[r]);
            rmax = max(rmax, h[r]);
            r--;
        }
    }

    cout << ans << endl;
    return 0;
}