当前位置: 首页 > news >正文

网络营销方案的制定五行seo博客

网络营销方案的制定,五行seo博客,怎样做网站用的大于9kb,装修效果图软件接雨水问题 问题背景 LeetCode 42. 接雨水 接雨水问题是一个经典的计算雨水滞留量的问题,通常使用柱状图来表示不同高度的柱子。在下雨的情况下,柱子之间的凹陷部分能够存储雨水,问题的目标是计算这些柱子所能接收的雨水总量。 相关知识 …

接雨水问题

问题背景

LeetCode 42. 接雨水
接雨水问题是一个经典的计算雨水滞留量的问题,通常使用柱状图来表示不同高度的柱子。在下雨的情况下,柱子之间的凹陷部分能够存储雨水,问题的目标是计算这些柱子所能接收的雨水总量。

相关知识

在解决接雨水问题之前,需要了解以下几个关键概念:

  • 柱状图:表示不同高度的柱子,通常由一个整数数组表示,每个元素代表柱子的高度。
  • 雨水滞留:在柱状图中,两根柱子之间的凹陷部分可以存储雨水,我们需要计算这些凹陷部分的总容量。

问题介绍

给定一个由非负整数表示的柱状图,每个柱子的宽度为 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

解题思路

接雨水问题的解决思路通常使用双指针法。具体步骤如下:

  1. 初始化左指针 left 和右指针 right,并初始化左侧最大高度 leftMax 和右侧最大高度 rightMax 为 0。
  2. 使用 leftright 指针从两端向中间遍历柱子,每次比较 leftright 指针所指的柱子高度,并更新左侧最大高度 leftMax 和右侧最大高度 rightMax
  3. 如果 height[left] < height[right],说明左侧的最大高度决定了当前位置能接收的雨水高度,计算并累加雨水量,然后将 left 指针向右移动一位;否则,右侧的最大高度决定了雨水高度,计算并累加雨水量,然后将 right 指针向左移动一位。
  4. 重复步骤 2 和步骤 3,直到 leftright 指针相遇。

最终,累加的雨水量即为所求的雨水滞留量。

代码实现

class Solution:def trap(self, height: List[int]) -> int:# 初始化结果为0res = 0# 初始化左指针left和右指针rightleft, right = 0, len(height) - 1# 初始化左侧最大高度leftMax和右侧最大高度rightMaxleftMax = rightMax = 0# 当左指针小于右指针时,继续循环while left < right:# 更新左侧最大高度leftMaxleftMax = max(leftMax, height[left])# 更新右侧最大高度rightMaxrightMax = max(rightMax, height[right])# 如果左侧当前高度小于右侧当前高度if height[left] < height[right]:# 计算当前位置能接的雨水量并累加到结果中res += leftMax - height[left]# 移动左指针向右移动一位left += 1else:# 否则,计算当前位置能接的雨水量并累加到结果中res += rightMax - height[right]# 移动右指针向左移动一位right -= 1# 返回最终结果return res

上述 Python 代码实现了双指针法的思路。首先,我们初始化左指针 left 和右指针 right,以及左侧最大高度 leftMax 和右侧最大高度 rightMax。然后,使用指针从两端向中间遍历柱子,计算并累加雨水量。最后,返回累加的雨水量作为结果。

时间和空间复杂度

  • 时间复杂度:双指针法的时间复杂度为 O(n),其中 n 是柱子的数量。
  • 空间复杂度:双指针法只需要常数级别的额外空间,空间复杂度为 O(1)。

结论

接雨水问题是一个经典的算法问题,通过双指针法,我们可以高效地计算雨水滞留量。

http://www.ritt.cn/news/12327.html

相关文章:

  • 广州番禺钟村聊城优化seo
  • 全国做网站的大公司有哪些关键词在线试听
  • 网站客服是做什么的武汉百度推广公司
  • 做网站实训心得360广告推广平台
  • 织梦做双语网站福州seo结算
  • 做网站简单还是做app简单专业网络推广公司排名
  • 国外建设网站流程东莞网站优化关键词排名
  • 呼和浩特做网站正规百度推广
  • 如何给网站增加外链seo和sem推广
  • 做网站的天空网网络广告的形式有哪些?
  • 如何分析竞争对手的网站市场营销策划方案书
  • 临西网站建设费用seo这个行业怎么样
  • 网站评论 设计百度的官方网站
  • 很多网站的微信登录怎么做台州网站建设
  • 广州市天河区网站设计公司百度怎么优化网站排名
  • 自己制作一个网站需要多少钱凡科建站靠谱吗
  • 网站资料清单seo运营学校
  • 企业建站1年网站的宣传推广方式
  • 自适应网站和响应式网站的区别软考十大最靠谱it培训机构
  • b2b2c网站建设谷歌浏览器怎么下载
  • 什么是传统网站韩国比分预测
  • 视频网站用什么做的关键词排名 收录 查询
  • 网站建设原因分析广告做到百度第一页
  • 网站如何做反爬百度指数批量
  • 注册公司那家网站做的比较好微博付费推广有用吗
  • 性价比最高网站建设价格焦作关键词优化排名
  • 网站模板下载免费橘子seo历史查询
  • 做博彩网站的虚拟空间seo站群优化
  • 网站开发属于什么专业旅游最新资讯 新闻
  • 静态html网站打包成exe淘宝搜索关键词排名查询工具