当前位置:网站首页>Analysis of rainwater connection
Analysis of rainwater connection
2022-07-06 19:30:00 【Little straw hat】
Title Description
Given n Nonnegative integers indicate that each width is 1 Height map of columns of , Calculate columns arranged in this way , How much rain can be received after rain .
Example 1:
Input :height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output :6
explain : Above is an array of [0,1,0,2,1,0,1,3,2,1,2,1] Height map of representation , under these circumstances , Can connect 6 Units of rain ( The blue part indicates rain ).
Example 2:
Input :height = [4,2,0,3,2,5]
Output :9
source : Power button (LeetCode)
link :https://leetcode.cn/problems/trapping-rain-water
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Method : Double pointer
Maximum water intake at each location = The left and right pointer positions correspond to the current maximum height corresponding to the endpoint of the end with small height - The height of the current position
utilize left and right The pointer scans from both ends of the array .
Judge the water receiving volume and pointer movement conditions .
Always give priority to moving the pointer with small height of the left and right pointer positions .
Code
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: // Calculate from the left and right ends
leftMax = max(leftMax, height[left]) // Update the maximum height of the left endpoint
rightMax = max(rightMax, height[right]) // Update the maximum height of the right endpoint
if height[left] < height[right]: // Determine the size of the left endpoint and the right endpoint , Move the small end towards the middle
ans += leftMax - height[left] // Calculate the maximum rainwater that can be connected to the left end point
left += 1
else:
ans += rightMax - height[right] // Calculate the maximum rainwater that can be connected to the right end
right -= 1
return ans
边栏推荐
- Meilu biological IPO was terminated: the annual revenue was 385million, and Chen Lin was the actual controller
- About image reading and processing, etc
- 潇洒郎: AttributeError: partially initialized module ‘cv2‘ has no attribute ‘gapi_wip_gst_GStreamerPipe
- Zero foundation entry polardb-x: build a highly available system and link the big data screen
- Pychrm Community Edition calls matplotlib pyplot. Solution of imshow() function image not popping up
- Is not a drawable (color or path): the vector graph downloaded externally cannot be called when it is put into mipmap, and the calling error program crashes
- [translation] linkerd's adoption rate in Europe and North America exceeded istio, with an increase of 118% in 2021.
- MySQL information Schema Learning (i) - - General table
- Solution of intelligent management platform for suppliers in hardware and electromechanical industry: optimize supply chain management and drive enterprise performance growth
- Test technology stack arrangement -- self cultivation of test development engineers
猜你喜欢
LeetCode_双指针_中等_61. 旋转链表
Druid database connection pool details
全套教学资料,阿里快手拼多多等7家大厂Android面试真题
It's super detailed in history. It's too late for you to read this information if you want to find a job
Spark foundation -scala
Documents to be used in IC design process
Live broadcast today | the 2022 Hongji ecological partnership conference of "Renji collaboration has come" is ready to go
今日直播 | “人玑协同 未来已来”2022弘玑生态伙伴大会蓄势待发
Systematic and detailed explanation of redis operation hash type data (with source code analysis and test results)
A popular explanation will help you get started
随机推荐
Elastic search indexes are often deleted [closed] - elastic search indexes gets deleted frequently [closed]
全套教学资料,阿里快手拼多多等7家大厂Android面试真题
How to do smoke test
Swiftui game source code Encyclopedia of Snake game based on geometryreader and preference
黑馬--Redis篇
LeetCode_ Double pointer_ Medium_ 61. rotating linked list
Live broadcast today | the 2022 Hongji ecological partnership conference of "Renji collaboration has come" is ready to go
[translation] micro survey of cloud native observation ability. Prometheus leads the trend, but there are still obstacles to understanding the health of the system
short i =1; i=i+1与short i=1; i+=1的区别
【翻译】Linkerd在欧洲和北美的采用率超过了Istio,2021年增长118%。
Solution of commercial supply chain management platform for packaging industry: layout smart supply system and digitally integrate the supply chain of packaging industry
学习探索-无缝轮播图
Is not a drawable (color or path): the vector graph downloaded externally cannot be called when it is put into mipmap, and the calling error program crashes
反射及在运用过程中出现的IllegalAccessException异常
Pytorch common loss function
关于图像的读取及处理等
swagger2报错Illegal DefaultValue null for parameter type integer
Looting iii[post sequence traversal and backtracking + dynamic planning]
The second day of rhcsa study
1805. 字符串中不同整数的数目