降水量

//两次遍历分别找到从起始点到该点的最大高度和从终点到该点的最大高度，且高度最低取0
//再次遍历，每个点的的雨水量等于该点左右最大高度中较低者减去该点高度


#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int>height(n,0);
	vector<int>maxL(n,0);
	vector<int>maxR(n,0);
	int tmp;
	for (int i = 0; i < n; i++) {
		cin >> height[i];
	}
	int max = 0;
	for (int i = 0; i < n; i++) {
		max = height[i] > max ? height[i] : max;
		maxL[i] = max;
	}
	max = 0;
	for (int i = n - 1; i >= 0; i--) {
		max = height[i] > max ? height[i] : max;
		maxR[i] = max;
	}
	int count = 0;
	for (int i = 0; i < n; i++) {
		int small = maxL[i] < maxR[i] ? maxL[i] : maxR[i];
		count += (small - height[i]);
	}
	cout << count;
	system("pause");
	return 0;
}

def trap(height):
    def stepv(num):
        temp = 0
        out = 0
        for i in num:
            if i < temp:
                out += temp
            else:
                out += i
                temp = i
        return out, temp

    height2 = height[::-1]
    v1, maxh = stepv(height)
    v2, maxh = stepv(height2)
    return v1 + v2 - len(height) * maxh - sum(height)

n = int(input())
l = list(map(int,input().split(" ")))
print(trap(l))

{

    if (index == length -1)
        return 0;

    //凹洞左边的最高点
    int lowTrend = index;
    //凹洞右边的最高点
    int highTrend = index;
    //当前访问的点
    int visitIndex = index;
    //凹洞最低的点
    int lowtestIndex = index;

    while (visitIndex<length)
    {
        //向下降的趋势，则这块有可能积水，且是目前最高点
        if (visitIndex < length-1 &&water[visitIndex] > water[visitIndex + 1])
        {
            lowTrend = visitIndex;
            ++visitIndex;

            //找到最低点
            while (visitIndex < length-1 && water[visitIndex] > water[visitIndex + 1])
            {
                ++visitIndex;
            }
            //没有向上的趋势
            if (visitIndex == length - 1 && water[visitIndex] < water[visitIndex - 1])
            {
                return 0;
            }

            lowtestIndex = visitIndex - 1;

            //找到最高点
            while (visitIndex < length - 1 && water[visitIndex] < water[visitIndex + 1])
            {
                ++visitIndex;
            }
            
            //最高点
            
            highTrend = visitIndex;


            //计算坑里面的体积
            int liquidVolume = 0;
            //蓄水高度参照
            int compareNum = 0;
            //比较向下趋势的最高点，与向上趋势的最高点，谁高
            if (water[lowTrend] > water[highTrend])
            {
                compareNum = water[highTrend];
            }
            else 
            {
                compareNum = water[lowTrend];
            }
            
            for (int addIndex = lowTrend + 1; addIndex < highTrend; ++addIndex)
            {
                liquidVolume += water[addIndex];
            }

            liquidVolume = (highTrend - lowTrend - 1)*compareNum - liquidVolume;

            return liquidVolume + getWaterVolume(water, highTrend, length);


        }
        else//向上升的趋势，则这块无法积水
        {
            ++visitIndex;
        }
    }

    return 0;

}