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

宿州公司做网站营销型公司网站建设

宿州公司做网站,营销型公司网站建设,百草味网络营销策划方案,wordpress升级无法创建目录题目描述 给定 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…

题目描述

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

示例 1:

img

输入: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

解题思路:

1.暴力解答:

每个位置处的积水取决于左右两边柱子的最低高度,分别从起始位置遍历到该位置得到左边的最高高度,然后从该位置遍历到末端,得到右边高度的最高值。因此计算每个位置处的积水量:等于该位置左右两边最高高度的最小值-该位置的高度。

代码:

class Solution {public static int trap(int[] height) {int sumVolume = 0;int i=0,len=height.length;for(;i<len;i++){int j=0,leftmax = i;while(j<i){if(height[j]>height[leftmax])leftmax = j;j++;}j=i+1;int rightmax = i;while(j<len){if(height[j]>height[rightmax])rightmax = j;j++;}sumVolume+=Math.min(height[leftmax],height[rightmax])-height[i];}return sumVolume;}
}

结果:
在这里插入图片描述

2.动态规划

上述暴力解法由于每次遍历i时都又遍历了一整遍数组,因此时间复杂度为O(n^2),导致运行时间超时。因此采用动态规划的思想,提前遍历数组,确定好每个位置处的左边最高值和右边最高值。然后再按上述计算积水量方法计算总的积水量即可。
代码:

class Solution {public static int trap(int[] height) {int sumVolume = 0;int i=0,len=height.length;int curMaxHeight = 0;int[] leftMaxheigt = new int[len]; // 存储每个位置左边最高值int[] rightMaxheigt = new int[len]; // 存储每个位置右边最高值for(;i<len;i++){// 从前往后遍历height数组获取每个位置左边最高值if(height[i]>curMaxHeight){curMaxHeight = height[i];}leftMaxheigt[i] = curMaxHeight;}curMaxHeight=0;for(i=len-1;i>=0;i--){// 从后往前遍历height数组获取每个位置右边最高值if(height[i]>curMaxHeight){curMaxHeight = height[i];}rightMaxheigt[i] = curMaxHeight;}for(i=0;i<len;i++){sumVolume+=Math.min(leftMaxheigt[i],rightMaxheigt[i])-height[i];}return sumVolume;}
}

结果:
在这里插入图片描述

3.双指针

在动态规划的基础上,不使用两个数组存储每个位置的左边最大高度和右边最大高度,而是一开始定义两个指针i,j,一开始分别指向数组第一个元素和数组最后一个元素,同时定义一个左边最高高度变量leftMax=0和一个右边最高高度变量rightMax=0。通过比较两个位置的高度,移动较矮的一方,当

class Solution {public static int trap(int[] height) {int i=0,j=height.length-1;int leftMax=0,rightMax=0;int sumVolume=0;while(i<j){if(height[i]<height[j]){if(height[i]<leftMax){sumVolume += leftMax-height[i];}else{leftMax=height[i];}i++;}else{if(height[j]<rightMax){sumVolume += rightMax-height[j];}else{rightMax=height[j];}j--;}}return sumVolume;}
}

结果:
在这里插入图片描述

http://www.hrbkazy.com/news/20510.html

相关文章:

  • 网站推广服务怎么做怎么找百度客服
  • 怎么做美食的视频网站seo教程下载
  • 做网站图片路径做缓存吗产品宣传推广策划
  • 网站建设与管理说课ppt网络项目资源网
  • 做彩票网站需要什么谷歌商店下载官方正版
  • 沧州网站建设制作苏州推广排名
  • 四川城乡住房城乡建设厅网站手机百度高级搜索入口在哪里
  • 自己做网站分销做百度推广一个月多少钱
  • a3电子报在什么网站做腾讯第三季度营收448亿元
  • 西安网站建设sxyun百度seo怎么查排名
  • 专业做数据的网站有哪些方面怎么让付费网站免费
  • 如何在百度建立自己的网站公司网站建设费
  • 合肥网站建设推荐 晨飞网络营销策划的十个步骤
  • 怎么做企业网站建设浙江百度推广
  • Vs做的网站调试时如何适应网页seo推广招聘
  • 云南网是什么网站百度学术官网
  • 帝国网站管理系统教程信息流广告接单平台
  • 域名服务器ip查询seoul是哪个城市
  • 网站如何做微信支付宝支付宝支付宝谷歌seo搜索引擎下载
  • 学校门户网站的网站建设方案网站文章优化技巧
  • 甘肃手机版建站系统价格网站seo优化步骤
  • 外包做网站哪家好wix网站制作
  • 常州网站制作公司有哪些互联网营销是做什么的
  • 网站建设如何找客户最近大事件新闻
  • 做网站的感觉朋友圈广告投放价格表
  • 开源企业建站系统哪个好网络营销的原理
  • 巴中住房建设部网站网站查找工具
  • 个人做淘宝客网站要备案吗网络客服
  • 电子商务网站规划与建设论文阿里指数app下载
  • 免费做网络推广的网站可靠吗企业培训课程有哪些