LeetCode42——Trapping Rain Water-蒲公英云

LeetCode42——Trapping Rain Water

题意：

看图就很明显。

但是做起来就没想象的简单了。。。

我最初的疑惑：

如果序列是这种情况01010，也就是说“凹点”两边都是“凸点”这样就简单了，直接根据短板原理可求，遍历求出索引为i-1和i+1的value的最小值即可。。。

但是如果遇到这种情况21012，也就是中间0的凹点，两边的壁呈递增，就懵逼了。。。

想了很久，口述还是不清楚，画个图吧：

SouthEast

图就一目了然了，事实上，我们把索引2处的水注与索引1,3的水分开成单独的水柱（虽然物理上不可能），那么在求解的时候，分别算出索引2处左右的最长的“隔板”（这里可以是隔空的），再求出这两者的最小值，减去索引2处的高度（此处为0），就是索引2处矩形水柱的高度了。

代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int curMax = 0;
        int len = height.size();
        vector<int>leftMax(len);
        vector<int>rightMax(len);
        for (int i = 0; i < len; i++)
        {
            leftMax[i] = curMax;//左边最大值
            curMax = max(curMax, height[i]);//当前最大值
        }
        curMax = 0;
        for (int i = len - 1; i >= 0; i--)
        {
            rightMax[i] = curMax;
            curMax = max(curMax,height[i]);
        }
        int sum=0;
        for (int i = 0; i < len; i++)
        {
            if (leftMax[i] != 0 && rightMax[i] != 0)
            {
                int temp = min(leftMax[i], rightMax[i]) - height[i];
                if (temp > 0)
                    sum += temp;
            }
        }
        //debuging
        //while (1)
        //{
        //    int a;
        //    int b;
        //}
        return sum;
    }
};