42. Trapping Rain Water

图解解题思路

首先往左边寻找比当前位置高度的的，往左边寻找时在未遇到比当前高时，遇到相等的表示之前已经找不，就不需要在去找了，因为之前已经找过，以下代码是从左开始遍历的
在往右边寻找比当前位置大的
在寻找过程中，计算宽度，高度使用找到的两边的最小的高度减去当前的高度，结果加上该宽度和高度的乘积
在寻找过程中，需要注意越界问题

class Solution {
    public int trap(int[] height) {
        int res = 0;
        for(int i=1; i<height.length-1; i++){
            int tmp=1;
            int lft=i-1;
            int rht=i+1;
            boolean isRepeated = false;
            while(lft>=0&&height[lft]<=height[i]){
                
                if(height[lft]==height[i]){
                    isRepeated = true;
                    break;
                }
                tmp++;
                lft--;
            }
            
            if(isRepeated)continue;
            
            
            while(rht<height.length&&height[rht]<=height[i]){
                tmp++;
                rht++;
            }
            if(lft>=0&&rht<height.length){
                //System.out.println(i+" "+ tmp +" " + height[lft]+" " + height[rht]);
                res += tmp*(Math.min(height[lft],height[rht])-height[i]); 
            }
        }
        return res;
        
    }
}

42. Trapping Rain Water

42. Trapping Rain Water

Comments

Links

Categories

Recent

Archives

Tags

Your browser is out-of-date!