题解 | #接雨水问题#
接雨水问题
https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
class Solution { public: long long sumPlus(long long i, long long j, vector<int>& arr, long long maxIndex = -1) { if ((maxIndex - i) <= 1) return 0; long long minV = min(arr[i], arr[j]); long long sum = 0; long long sumlow = 0; if (maxIndex > 0) { while (j <= maxIndex) { long long minV = min(arr[i], arr[j]); if (arr[i] > arr[j]) { sumlow += minV; j++; } else { sum += ((j - i + 1) * minV - (2 * minV + sumlow)); i = j; j++; sumlow = 0; } } } return sum >= 0 ? sum : 0; } long long maxWater(vector<int>& arr) { int len = arr.size(); if (len < 2) return 0; long long sum = 0; auto iteratorMaxN = max_element(arr.begin(), arr.end()); long long maxN = *iteratorMaxN; long long maxNIndex = distance(arr.begin(), iteratorMaxN); sum += sumPlus(0, 1, arr, maxNIndex); if (len - maxNIndex >= 2) { reverse(arr.begin() + maxNIndex, arr.end()); sum += sumPlus(maxNIndex, maxNIndex + 1, arr, len - 1); } return sum; } };