当前位置:网站首页>接雨水问题解析
接雨水问题解析
2022-07-06 11:32:00 【小小草帽】
题目描述
给定 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
方法:双指针
每个位置的最大接水量 = 左右指针位置对应高度小的一端的端点对应的当前最大高度 - 当前位置的高度
利用left和right指针分别从数组两端扫描。
判断接水量和指针移动条件。
总是优先移动左右指针位置高度小的指针。
代码
class Solution(object):
def trap(self, height):
""" :type height: List[int] :rtype: int """
ans = 0
left, right = 0, len(height) - 1
leftMax = rightMax = 0
while left < right: //从左右两端开始计算
leftMax = max(leftMax, height[left]) //更新左端点最大高度
rightMax = max(rightMax, height[right]) //更新右端点最大高度
if height[left] < height[right]: //判断左端点和右端点的大小,将高度小的一端向中间移动
ans += leftMax - height[left] //计算左端点可以接的最大雨水
left += 1
else:
ans += rightMax - height[right] //计算右端点可以接的最大雨水
right -= 1
return ans
边栏推荐
- CPU负载很低,loadavg很高处理方法
- Sanmian ant financial successfully got the offer, and has experience in Android development agency recruitment and interview
- Multithreading Basics: basic concepts of threads and creation of threads
- 零基础入门PolarDB-X:搭建高可用系统并联动数据大屏
- test about BinaryTree
- AutoCAD - what is the default lineweight for centerline drawing and CAD? Can I modify it?
- [pytorch] yolov5 train your own data set
- Qlabel marquee text display
- Documents to be used in IC design process
- R language uses rchisq function to generate random numbers that conform to Chi square distribution, and uses plot function to visualize random numbers that conform to Chi square distribution
猜你喜欢
受益匪浅,安卓面试问题
Yutai micro rushes to the scientific innovation board: Huawei and Xiaomi fund are shareholders to raise 1.3 billion
Don't miss this underestimated movie because of controversy!
MRO工业品企业采购系统:如何精细化采购协同管理?想要升级的工业品企业必看!
Wx applet learning notes day01
JDBC details
Simple understanding of MySQL database
Actf 2022 came to a successful conclusion, and 0ops team won the second consecutive championship!!
Understanding disentangling in β- VAE paper reading notes
黑馬--Redis篇
随机推荐
[pytorch] yolov5 train your own data set
[depth first search] Ji suanke: find numbers
Fast power template for inverse element, the role of inverse element and example [the 20th summer competition of Shanghai University Programming League] permutation counting
R language ggplot2 visualization: use the ggstripchart function of ggpubr package to visualize the grouped dot strip plot, and set the add parameter to add box plots for different levels of dot strip
C # use Marshall to manually create unmanaged memory in the heap and use
In 50W, what have I done right?
QLabel 跑马灯文字显示
Wx applet learning notes day01
三年Android开发,2022疫情期间八家大厂的Android面试经历和真题整理
JDBC details
R语言ggplot2可视化:使用ggpubr包的ggdotplot函数可视化点阵图(dot plot)、设置palette参数设置不同水平点阵图数据点和箱图的颜色
Countdown 2 days | live broadcast preview of Tencent cloud message queue data import platform
QPushButton绑定快捷键的注意事项
LeetCode-1279. Traffic light intersection
渲大师携手向日葵,远控赋能云渲染及GPU算力服务
ModuleNotFoundError: No module named ‘PIL‘解决方法
Xingnuochi technology's IPO was terminated: it was planned to raise 350million yuan, with an annual revenue of 367million yuan
R language ggplot2 visualization: use ggviolin function of ggpubr package to visualize violin diagram
[depth first search] Ji suanke: Square
Master Xuan joined hands with sunflower to remotely control enabling cloud rendering and GPU computing services