#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * max water * @param arr int整型vector the array * @return long长整型 */ long long maxWater(vector<int>& arr) { // write code here // 双指针 int n=arr.size(); // 从左又向右投影,找出每条柱子在 已遍历的柱子中的最大值; vector<int> left_right(n,0); // 从右又向左投影,找出每条柱子在 已遍历的柱子中的最大值; vector<int> right_left(n,0); // 然后再次遍历数组arr,每条柱子从left_right和right_left中选出较小的值,减去当前柱子的长度,即为该柱子能存储的雨水量; // 其实就是找出当前柱子左右两边围起来区域的较矮的墙; for(int left=0; left<n; ++left) { if(left==0) left_right[left] = arr[left]; else left_right[left] = max(left_right[left-1], arr[left]); } for(int right=n-1; right>=0; --right) { if(right==n-1) right_left[right] = arr[right]; else right_left[right] = max(right_left[right+1], arr[right]); } int ans = 0; // 其实可以集成在第二次遍历中就来计算; // 算了,还是这样思路清晰点 for(int i=0; i<n; ++i) ans += (min(left_right[i],right_left[i]) - arr[i]); return ans; } };