Leetcode 42.接雨水【C++】

地址：https://leetcode-cn.com/problems/trapping-rain-water/

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

一开始做的时候，思路错了，到代码都写出来了才发现，然后又重新来一遍~

首先，要能接住雨水说明两边高中间低，我们就总是以当前的点为左侧的最高点，默认在右侧总能找到比我们以为的最高点大的数，那么问题就简化了。

我们只需要遍历数组，起始处默认 height[0] 就是左侧的最高点，始终认为 height[left] - height[i] 的水量是可以接住的，遇到大于 height[left] 的数说明遇到了右侧最高点，同时也就表面我们前面的假设成立了，此时再更新 left 继续以同样的方法计算。如果恰好最后一个 height[left] 是小于 height.back() 的，那么遍历完一次数组就得到了结果。

但事实上可能 height.back() 是小于最后的 height[left] 的。例如假如最后一部分数组是 [5,1,2,4] ，我们默认 5 为左侧的最大值，并认为右侧能找到大于 5 的数，然后我们分别为总水量 water 加上了 (5-5)+(5-1)+(5-2)+(5-4) = 8 ，这就导致得到了错误的结果。

解决的办法是，按前述假设遍历完一次数组后，判断 height.back() < height[left] ，如果很不幸遇到了这样的情况，那么我们就反过来以同样的思路从后往前遍历到 left 下标处即可。也就是将 height.back() 作为右侧最高点，而现在我们清楚的知道往前遍历到 left 下标处 height[left] > height[right] 一定是成立的。以上述例子为例，也就是 [5,1,2,4] 从后往前遍历，首先减掉之前错误的水量，同时为总水量加上正确的水量 (4-4)+(4-2)+(4-1) = 5 。

代码

class Solution {
public:
    int trap(vector<int>& height) {
        //至少要三个柱子才可能接住雨水
        if (height.size() < 3)
            return 0;
        int water = 0;
        int left = 0;//左高点
        for (int i = 0; i < height.size(); i++) {
            if (height[i] >= height[left]) {
                left = i;
            }
            water += height[left] - height[i];
        }
        if (height.back() < height[left]) {
            int right = height.size() - 1;//右高点
            for (int i = height.size() - 1; i > left; i--) {
                water -= height[left] - height[i];
                if (height[i] >= height[right])
                    right = i;
                water += height[right] - height[i];
            }
        }
        return water;
    }
};