题解 | #接雨水问题#

参考自https://blog.nowcoder.net/n/155d424724d0472e9d534ccc5551b40a?f=comment
因为能够容水，必然是处于凹陷处，假设凹陷处为i位置，那么i位置的容水应该是i处左边的最大值，和i处右边的最大值取最小的一个 然后减去arr[i]不能容水的量。所以需要保存每个位置i处左边的最大值，即从左往右保存当前最大值；和i处右边的最大值，即从右往左保存当前最大值；且如果能保存水的时候(min(la[i], ra[i]) - arr[i] > 0)，才能算入容量。

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        int length = arr.size();
        vector<int> left_max_arr(length, 0);
        vector<int> right_max_arr(length, 0);
        left_max_arr.at(0) = arr.at(0);
        right_max_arr.at(length - 1) = arr.at(length - 1);
        for(int i = 1; i < length - 1; ++i)
        {
            left_max_arr.at(i) = std::max(left_max_arr.at(i - 1), arr.at(i));
            right_max_arr.at(length -1 -i) =
                std::max(right_max_arr.at(length -i), arr.at(length - 1 - i));
        }
        long long sum = 0;
        for(int i = 1; i < length - 1; ++i)
        {
            int min  = std::min(left_max_arr.at(i), right_max_arr.at(i));
            if( min - arr.at(i) > 0)
                sum += min - arr.at(i);
        }
        return sum;
    }
};