美文网首页算法相关
3种方法: 计算接最多的雨水

3种方法: 计算接最多的雨水

作者: suoxd123 | 来源:发表于2020-04-04 23:16 被阅读0次

题目

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

<center><img src="/img/alg/20200404104541992.png“></center>

示例:

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


解法一(暴力法)

思路:在每个位置,分别向左和向右找雨水的边界,从而得到雨水在当前位置的深度,累加每个位置的深度即为所求。

  1. 对整个区域的每个位置进行计算
  2. 分别向左和向右寻找边界值,然后取得两个边界值的最小值,作为当前水量高度
  3. 累加所有坐标的水量
  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)
//author: suoxd123@126.com
int trap(int* height, int heightSize){
    int cnt = 0, rightIdx, rightVal, leftIdx, leftVal;
    for(int k=0; k<heightSize; k++){
        rightIdx = k;
        rightVal = height[k];
        leftIdx = k;
        leftVal = height[k];
        for(int i=0; i<k; i++){//向左找最大值
            if(height[i] > leftVal){
                leftVal = height[i];
                leftIdx = i;
            }
        }
        for(int i=k+1; i<heightSize; i++){//向右找最大值
            if(height[i] > rightVal){
                rightVal = height[i];
                rightIdx = i;
            }
        }
        cnt += (leftVal> rightVal?rightVal:leftVal) - height[k];
    }
    return cnt;
}

解法二(动态规划)

思路:基于解法一进行优化,解法一每个位置都要遍历整个区间来寻找左右最大值,可以基于动态规划的思想,分别从左右两边开始寻找当前位置的左右方向的最大值,因此执行时间从N2变为2N。

  1. 申请临时空间,分别用于存储当前坐标,左右两边的最大值
  2. 从左边开始向右寻找每个左边能看到的最大值,右边同理
  3. 累加所有坐标的水量
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
//author: suoxd123@126.com
int trap(int* height, int heightSize){
    if(heightSize == 0) return 0;
    int cnt = 0, *leftMax, *rightMax;//临时变量保持各位置的左右最大值
    leftMax = (int *)malloc(sizeof(int)*heightSize);
    rightMax = (int *)malloc(sizeof(int)*heightSize);
    memset(leftMax,0,heightSize);
    memset(rightMax,0,heightSize);
    leftMax[0] = height[0];
    for(int i=1;i<heightSize;i++){//左边最大值
        leftMax[i] = leftMax[i-1] > height[i]?leftMax[i-1]:height[i];
    }
    rightMax[heightSize - 1] = height[heightSize - 1];
    for(int i=heightSize - 2;i>=0;i--){//右边最大值
        rightMax[i] = rightMax[i+1] > height[i]?rightMax[i+1]:height[i];
    }
    for(int i=0; i<heightSize; i++){
        cnt += (leftMax[i]> rightMax[i]?rightMax[i]:leftMax[i]) - height[i];
    }
    free(leftMax)
    free(rightMax)    
    return cnt;
}

解法三(双指针法)

思路:基于解法二进行优化,由于求出一个位置左右两边最大值后,仅使用其中较小的值,并舍弃较大一边的值,因此不必找到每个位置左右两边的最大值,而是只要找到左右两边最大值中较小的值即可。

使用两个指针,来标志左右两边的位置值,并不断向中间递进,如果坐标值大则右边指针一直向左边移动,反之亦然,每个位置计算时候都是左右两边的最大值中的较小值。

  1. 左边最大值从左向右移动,右边最大值从右向左移动,左右两个指针相遇后,循环结束
  2. 左边值如果大于右边,则计算右边当前储水量,并且右边指针向左移动,反之同理
  3. 分别记录两边的最大值,用于计算每个位置的储水量,储水量等于最大值减去当前值
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
//author: suoxd123@126.com
int trap(int* height, int heightSize){
    int cnt = 0, rightIdx = heightSize - 1, rightVal = 0, leftIdx = 0, leftVal = 0;
    while(leftIdx <= rightIdx){
        if(leftVal < rightVal){//最大值在右边
            if(height[leftIdx] > leftVal){//存储左边新的最大值
                leftVal = height[leftIdx];
            }
            else{//基于左边值计算储水量
                cnt += leftVal - height[leftIdx];
            }
            leftIdx ++;
        }
        else{
            if(height[rightIdx] > rightVal){//记录右边最大值
                rightVal = height[rightIdx];
            }
            else{
                cnt += rightVal - height[rightIdx];
                rightIdx --;
            }
        }
    }
    return cnt;
}

相关文章

  • 3种方法: 计算接最多的雨水

    题目 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由...

  • 算法题

    接雨水 动态规划:找到当前位置,min(max左边,max右边),与当前位置计算差值可以得到当前位置接的雨水。 优...

  • Java算法(3):接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 输入:heig...

  • 接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...

  • 接雨水

    题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/trap...

  • 接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...

  • 接雨水

    https://leetcode-cn.com/explore/interview/card/bytedance/...

  • 接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...

  • 接雨水

    来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/trappi...

  • 接雨水

    题目: 题目的理解: 从示例图中可以很好的理解,题目的意思,真的是题目描述越少越难。最直接的思路:(1)为一个高度...

网友评论

    本文标题:3种方法: 计算接最多的雨水

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