遍历两遍,从左往右遍历保存当前最大值,从右往左遍历保存当前最大值,然后容水量为 两次遍历最大值中的最小值减去当前arr[i]。累加起来即可。
class Solution { public: /** * max water * @param arr int整型vector the array * @return long长整型 */ long long maxWater(vector<int>& arr) { // write code here vector<int> la(arr.size(), 0); vector<int> ra(arr.size(), 0); int len = arr.size(); la[0] = arr[0]; ra[len-1] = arr[len-1]; for (int i = 1; i < arr.size(); i++) { la[i] = max(la[i-1], arr[i]); ra[len-i-1] = max(ra[len-i], arr[len-i-1]); } long long ans = 0; for (int i = 1; i < len-1; i++) { if (min(la[i], ra[i]) - arr[i] > 0) ans += min(la[i], ra[i]) - arr[i]; } return ans; } };