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

一个网站的构建百度学术官网

一个网站的构建,百度学术官网,微信公众号对接wordpress教程,广州市口碑seo推广力扣11. 盛最多水的容器 11. 盛最多水的容器 - 力扣(LeetCode) 难度 中等 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成…

力扣11. 盛最多水的容器

11. 盛最多水的容器 - 力扣(LeetCode)

难度 中等

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 10^4
class Solution {
public:int maxArea(vector<int>& height) {}
};

解析代码

首先想到的是两层循环的暴力解法,时间复杂度是O(N^2),这里采用双指针(对撞指针)的思想优化到O(N):

设两个指针 left , right 分别指向容器的左右两个端点,此时容器的容积 :
v = (right - left) * min( height[right], height[left]) 
容器的左边界为 height[left] ,右边界为 height[right] 。
为了方便叙述,假设「左边边界」小于「右边边界」。

  • 容器的宽度一定变小。
  • 由于左边界较小,决定了水的高度。如果改变左边界,新的水面高度不确定,但是一定不会超过右边的柱子高度,因此容器的容积可能会增大。
  • 如果改变右边界,无论右边界移动到哪里,新的水面的高度一定不会超过左边界,也就是不会超过现在的水面高度,但是由于容器的宽度减小,因此容器的容积一定会变小。

由此可见,左边界和其余边界的组合情况都可以舍去。所以可以left++跳过这个边界,继续去判断下一个左右边界。

不断重复上述过程,每次都可以舍去大量不必要的枚举过程,直到left与right相遇。期间产生的所有的容积里面的最大值,就是最终答案。

代码:

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while(left < right){int v = (right - left) * min(height[left], height[right]);ret = max(v, ret);if(height[left] < height[right]) // 哪个小哪个就往中间移动{++left;}else{--right;}}return ret;}
};
http://www.dinnco.com/news/36869.html

相关文章:

  • 网站首页index.html南宁百度快速优化
  • 重庆长寿网站设计公司哪家好河南网站顾问
  • 怎么知道网站的ftp广州百度推广优化排名
  • 网站系统测试计划即刻搜索
  • 站长要维护网站百度百科创建
  • 做汽车网站一句话让客户主动找你
  • 网站后台shopadmin输在哪里免费的网站推广
  • 广告公司怎么设置网站关键字南京市网站
  • 孝感注册公司肇庆seo外包公司
  • 网站建设如何记账南京百度
  • 企业邮箱地址怎么填seo比较好的公司
  • 随州做网站的公司学生网页设计模板
  • wordpress 网站首页可以打开_其他页面打不开网络营销公司是做什么的
  • 包年seo和整站优化google关键词查询工具
  • 定制网站开发公司seo高手培训
  • lamp网站开发黄金组...我想学做互联网怎么入手
  • 连云港网站建设手机百度云网页版登录
  • 今日头条网站模板网站查询seo
  • 可靠的武进网站建设网络营销软文范例300字
  • 中国建设银行官方网站沈阳网站优化包括哪些
  • 深圳做电商平台网站建设淮北网站建设
  • 邓州市网站建设2023年火爆的新闻
  • 如何做资源论坛网站admin5站长网
  • 怎样做网站推广啊网站查询工具
  • 广州在线网页制作工具seo顾问合同
  • 物流网站建设的背景seo系统培训班
  • 手工做火枪的网站整合营销传播
  • 公司网站做一下多少钱html简单网页代码
  • 邯郸景区网站制作营销型网站建设公司价格
  • 手机免费自建网站郑州seo学校