题解

难度：较难

知识点：分割字符串、数组、数学逻辑

解题思路：这道题主要在数学逻辑上具有较大的难度。解决这种数组问题，一定要想好数据的保存方式，再者这道题在输入中涉及到了字符串的分割，只有将字符串分割出来保存进数组才能使用这些数字。整道题将涉及到比较难的数学思维，以下将逐一介绍方法。

方法一：暴力解算（不能运行，运行超时，但是一种解决思维）

因为需要计算所有的盛水量，所以加入可以计算出每一个位置的盛水量，进行累加即可得到最终结果。但是怎么计算每一个位置的盛水量呢？这里只要确定每个位置，这需要寻找每一位置的左边界left和右边界right，然后比较[left, right]之间取较小值即可。

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<int> Heights;
    char c;
    int flag = 0;
    while((c = getchar()) != '\n'){
        if(c != ','){
            flag = flag  * 10 + (c - '0');
        } else {
            Heights.push_back(flag );
            flag = 0;
        }
    }
    Heights.push_back(flag);
    long Sum = 0;
    int len=Heights.size();
    for(int i=1;i<len-1;i++)
    {
        int LeftMax=0;
        int RightMax=0;
        for(int j = i - 1; j >= 0; j--)
            LeftMax= max(LeftMax,Heights[j]);
        for(int k=i+1;k<len;k++)
            RightMax= max(RightMax,Heights[k]);
        int minval = min(LeftMax, RightMax);
        if(minval > Heights[i])
            Sum += minval - Heights[i];
    }
    cout<<Sum<<endl;
    return 0;
}

方法二（暴力法的优化）

前面因为在每个位置都需要进行两个for循环，在整个运行过程中导致超时，所以可以进行优化，直接采用两个数组保存每个位置最大左、右边界值即可。

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<int> Heights;
    char c;
    int flag = 0;
    while((c = getchar()) != '\n'){
        if(c != ','){
            flag = flag * 10 + (c - '0');
        } else {
            Heights.push_back(flag );
            flag = 0;
        }
    }
    Heights.push_back(flag );
    long Sum = 0;
    int len=Heights.size();
    int left_max[len];
    int right_max[len];
    left_max[0] = Heights[0];
    right_max[len - 1] = Heights[len - 1];
    for (int i = 1; i < len; i++) {
        left_max[i] = max(Heights[i], left_max[i - 1]);
        right_max[len - i - 1] = max(Heights[len-i-1], right_max[len-i]);
    }
    for (int i = 1; i < len - 1; i++) {
        Sum += min(left_max[i], right_max[i]) - Heights[i];
    }
    cout<<Sum<<endl;
    return 0;
}

方法三（双指针逼近）

使用两个指针标记，夹近这个值。
（1）设置两个索引值：
左边界索引left和右边界索引right
左边界索引：从数组头到数组尾方向，第一次出现下降趋势的位置。
右边界索引：从数组尾到数组头方看，第一次出现下降趋势的那个索引的位置。
（2）记录左边界和右边界的高度，记作leftHeight和rightHeight。如果left < right，说明左右边界还没有重合，令left加1。如果left位置能够存储雨水，则更新结果的值。如果此位置不能存储雨水，需要进入下一轮循环，更新leftHeight的值。如果left < right，说明左右边界还没有重合，令right减1。如果right位置能够存储雨水，则更新结果的值。如果right位置不能存储雨水，进入下一轮循环，更新rightHeight的值。

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
int main()
{
    //分割这个字符串，将数字保存进vector里
    vector<int> Heights;
    char c;
    int flag = 0;
    while((c = getchar()) != '\n'){
        if(c != ','){
            flag = flag * 10 + (c - '0');
        } 
        else {
            Heights.push_back(flag);
            flag = 0;
        }
    }
    Heights.push_back(flag);
    long Sum = 0;
    int len=Heights.size();
    int left = 0;
    while(left < len - 1 && Heights[left + 1] >= Heights[left]) {
        left++;
    }
    int right = len - 1;
    while(right >= 1 && Heights[right - 1] >= Heights[right]) {
        right--;
    }
    while(left < right) {
        int leftHeight = Heights[left];
        int rightHeight = Heights[right];
        if(leftHeight <= rightHeight) {
            while(left < right) {
                left++;
                if(Heights[left] < leftHeight) {
                    Sum += leftHeight - Heights[left];
                }
                else
                    break;
            }
        }
        else {
            while(left < right) {
                right--;
                if(Heights[right] < rightHeight) {
                    Sum += rightHeight - Heights[right];
                }
                else
                    break;
            }
        }
    }
    cout<<Sum<<endl;
    return 0;
}