42. 接雨水

作者: geaus | 来源:发表于2020-02-22 22:22 被阅读0次

    题目描述

    给定n个非负整数表示宽度为1的柱子高度,按此排序下雨后能接多少水。


    image

    示例:

    输入: [0,1,0,2,1,0,1,3,2,1,2,1]
    输出: 6
    

    解题思路

    每个柱子可接的水量 = min(左边柱子高度,右边柱子高度) 与当前柱子高度的差。当然最左、最右柱子不可以接水。
    所以可以定义两个数组left和right,分别存储i左边柱子的最大高度、i右边柱子的最大高度。

    int trap(vector<int>& height){
        int length = height.size();
        if(length < 1)
            return 0;
    
        vector<int> left(length, 0);
        vector<Int> right(length, 0);
    
        int max_left = height[0];
        for(int i=1; i<length-1; i++){
            if(max_left<height[i])
                max_left = height[i];
            left[i] = max_left;
        }
    
        int max_right = height[length-1];
        for(int j=length-2; j>=0; j--){
            if(max_right<height[j])
                max_right = height[j];
            right[j] = max_right;
        }
    
        int ret = 0;
        for(int i=1; i<length-1; i++){
            int min_height = min(left[i], right[i]);
            ret += max(0, min_height-height[i]);
        }
        return ret;
    }
    

    更优解:双指针法,不需要设定left数组和right数组,仅保留max_left和max_right。这是因为计算每个位置的水量时,仅需要知道一边最小的高度就好。

    • 当当前左边界<右边界,收集left处的水,左边界++
    • 当当前左边界>有边界,收集right处的水,右边界--
        int trap(vector<int>& height) {
            int length = height.size();
            if(length<1)
                return 0;
    
            // max_left, 当前左边最大高度;max_right,当前右边最大高度
            int max_left = height[0], max_right = height[length-1];
            // left,当前左边收集下标;right,当前右边收集下标
            int left = 1, right = length - 2;
            int ret = 0;
            for(int i=1; i<length-1; i++){
                if(max_left<max_right){
                    max_left = max(height[left], max_left);
                    ret += max(0, max_left - height[left]);
                    left++;
                }else{
                    max_right = max(height[right], max_right);
                    ret += max(0, max_right - height[right]);
                    right--;
                }
            }
            
            return ret;
        }
    

    相关文章

      网友评论

        本文标题:42. 接雨水

        本文链接:https://www.haomeiwen.com/subject/bkvrqhtx.html