LeetCode42——Trapping Rain Water

本是古典何须时尚 2022-08-09 09:55 56阅读 0赞

题意：

看图就很明显。

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

我最初的疑惑：

如果序列是这种情况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;
    	}
    };

[SouthEast]: /images/20220731/5847b0fd03a1402b80d6db7a86023573.png