题解 | #接雨水问题#

#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;
    }
};