题解 | #接雨水问题#

其实这道题想通就不难。
接雨水的条件是，左边有木板大于这个高度，右边也有木板大于这个高度，就和下图类似。

如上我们可以知道两个条件：
（1）一个柱子能填充水一定是存在在左右两个边界的柱子大于这个柱子。
（2）一个柱子填充水之后的高度一定是左边最高的柱子和右边最高的柱子其中较小的一个的高度
由以上条件我们可以先更新左边界，然后再更新右边界，得到每个柱子被水填满之后的高度。
先扫描左边界，不断更新最大的的左边界。
如果当前高度小于左边界最大高度，就让水填充到最高高度（两端边界不需要更新）
如果当前高度大于等于最大高度，就更新最大高度，同时也填充到最高高度。
如下图所示：
这个步骤我们需要开辟一个数组，因为下一步扫描右边界我们也需要原来这个数组。

扫描完成后如下图。

然后我们需要更新右边界，
更新规则如下，
如果填充的高度大于了最大右边界，此时需要更新水填充后的高度，
注意此时有两种情况，情况一如下图

这个时候水填充后高度就是最大右边界。
情况二如下图

类似这种阶梯，因为水填充后的高度是不能低于柱子的高度，所以此时水填充后的高度是原来这个柱子高度，同时最大右边界也需要更新到这个柱子的高度。
二次扫描后如图

得到这个图以后求接到多少雨水也很容易了，直接按列相减求和就ok了。
代码如下

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        vector<int> L(arr.size(), 0);//对应填充后的图。
        int maxL = arr[0];//最大左边界
        for (int i = 1; i < L.size() - 1; i++) {
            if (arr[i] > maxL) {
                L[i] = arr[i];//如果当前柱子高度大于最大左边界，则更新最大左边界
                maxL = arr[i];
            }
            else
            {
                L[i] = maxL;//否则填充到最大左边界
            }
        }
        int maxR = arr[arr.size() - 1];//最大右边界
        for (int i = L.size() - 2; i > 0; i--) {
            if (L[i] > maxR) {
                if (maxR >= arr[i])
                    L[i] = maxR;//对应情况一，不需要更新最大右边界，直接更新填充高度就可以
                else
                {
                    L[i] = arr[i];//对应情况二，更新填充高度时也要更新最大右边界
                    maxR = arr[i];
                }
            }
        }
        long long n = 0;
        for (int i = 1; i < arr.size() - 1; i++) {//相减就可以直接求出填了多少水
            n += L[i] - arr[i];
        }
        return n;
    }
};