给定n个柱面的高度,表示降雨某地n块区域的海拔高度。
计算降雨之后该地最大储水面积。如果低于地平线,也就是小于0,则一定积水
//两次遍历分别找到从起始点到该点的最大高度和从终点到该点的最大高度,且高度最低取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))