首页 > 代码库 > 42. Trapping Rain Water

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

技术分享

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

 

 

此题与给小孩分糖那题很相似,都是可以左边遍历一遍,右边遍历一遍。

public int Trap(int[] height) {        int max =0;        int res = 0;        int size = height.Count();        if(size <= 2) return res;        var maxArr =new int[size];        for(int i = 0;i< height.Count();i++)        {            maxArr[i] =Math.Max(height[i],max);            max = Math.Max(max,height[i]);        }        int rightMost  =0;        int lessHeight = 0;        for(int i = size -1 ;i>=0;i--)        {            rightMost = Math.Max(rightMost, height[i]);            lessHeight = Math.Min(rightMost, maxArr[i]);            res +=  (lessHeight - height[i] > 0)?lessHeight - height[i] : 0;        }        return res;    }

 

参考OJ上大神的做法,用stack只存比peek值小的元素的index,因为index要用来算两个边之间的宽度。这个方法是将水分层了,也就是比如上图test case中间存水的部分,因为先出现1的右边边界,先加上1的水,后来又遇到3的边界,左边为1时没有水加入,左边为2时加入水,水的高度为更低的边与基地的差(Min(2,3)-1)。

 

 public int Trap(int[] height) {        int res = 0;        int size = height.Count();        if(size <= 2) return res;        int i =0;        var stack = new Stack<int>();//store the largerst heigth index        while(i< size)        {            if(stack.Count()==0 || height[i] <= height[stack.Peek()]) stack.Push(i++);            else            {                int bot = stack.Pop();                res += (stack.Count()==0)?0:((Math.Min(height[stack.Peek()], height[i]) - height[bot])*(i - stack.Peek()-1));;             }        }        return res;    }

 

42. Trapping Rain Water