力扣-42.接雨水

题目:

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


示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 
输出:6 
解释:上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示:

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

题解

将整个列表按照最大值 maxV 分成两部分,左边以及右边的所有的值都不可能超过最大值 maxV。

对于所有的左边值来说,可以将最大值 maxV 作为所有蓄水池的右边界。

而蓄水池的左边界则是从左到右遍历到当前值是的最大值。

最终的水平面将取决于值较小的边界,则为左边界。

def trap(height):
    maxI = np.argmax(height).flatten()[0]
    tr = i = 0
    for j in range(1, maxI):
        if height[i] > height[j]:
            tr += height[i] - height[j]
        else:
            i = j
    i = len(height) - 1
    for j in range(len(height) - 2, maxI, -1):
        if height[i] > height[j]:
            tr += height[i] - height[j]
        else:
            i = j
    return tr


 

相关推荐

  1. 42. 雨水

    2024-01-08 02:50:02       51 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-01-08 02:50:02       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-01-08 02:50:02       106 阅读
  3. 在Django里面运行非项目文件

    2024-01-08 02:50:02       87 阅读
  4. Python语言-面向对象

    2024-01-08 02:50:02       96 阅读

热门阅读

  1. 二叉树part02 算法

    2024-01-08 02:50:02       51 阅读
  2. 渗透第四天 (抽空再看一天 )

    2024-01-08 02:50:02       52 阅读
  3. 【Unity】云的渲染

    2024-01-08 02:50:02       67 阅读
  4. 一个奇怪的问题和奇怪的解决方案

    2024-01-08 02:50:02       73 阅读
  5. MySQL 8.0中新增的功能(四)

    2024-01-08 02:50:02       55 阅读
  6. uniapp表单验证

    2024-01-08 02:50:02       75 阅读
  7. Kubernets(K8S)启动和运行 01-02 Kubernetes的速度非常快

    2024-01-08 02:50:02       45 阅读
  8. C++ unordered_map用法总结

    2024-01-08 02:50:02       54 阅读
  9. spring之事务工作原理

    2024-01-08 02:50:02       56 阅读
  10. SpringCloud学习

    2024-01-08 02:50:02       62 阅读
  11. 基于Matlab的车道线检测技术研究与实现

    2024-01-08 02:50:02       62 阅读