CodeCollection2018
8/18/2019 - 11:32 AM

Leetcode--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.

Dynamic Programming
content_copyfile_download
public int trap(int[] height){
    int res = 0,mx = 0,n = height.length();
    int[] dp = new int[height.length]{0};
    for(int i = 0; i < height.length; i++){
        dp[i]=mx;
        mx = max(mx,height[i]);  //从左往右遍历得到i位置左边最大的高度
    }
    mx = 0;
    for(int i = height.length-1; i >=0; i--){
        dp[i]= min(dp[i],mx);  //从右往左遍历得到i位置右边最大的高度，并取左边最大高度和右边最大高度较小值
        mx=  max(mx,height[i]);//更新右边最大的高度
        id(dp[i]>height[i]) res += dp[i]-height[i];//res累加的是每一个bar上面会存多少水
    }
    return res;
}