题目内容

一条路高低不平，下雨时水会留在低洼的地方。

把路面简化成一个直线，用一个数组描述它的高低。

比如[3 2 4]代表一条$3$个单位长的路，高度依次为3 2 4，则下雨时，它的最大积水可以达到$1$。

实际一个计算最大积水的 函数，输入是代表描述路面高低的数组，输出是最大积水量

前缀最大值

对于一个路面的最左边和最右边，他们两的高度就类似于0，不可能积水，对于某一个位置来说，积水量 = min(左边的最大高度, 右边的最大高度) - 当前高度，就比如 1 4 2 5 3，中的2左边会被4挡住，右边会被5挡住，预处理pre,suf数组，prei代表第i个元素左边的的最大值(包括自己),suf代表右边，预处理完成后，枚举road,ans+=min(pre[i],suf[i])-road[i]即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define N 100005

signed main() {