Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
题意:给出n个非负值a1, a2, ..., an,(i, ai) 和 (i, 0)组成木桶的一边,找出木桶的两边使木桶
的容积最大
思路:也是一个双指针的题
1.两个指针i,j,当i<j时,不断两头往里面扫描
2.每扫描一个位置计算当前的面积,并刷新最大的面积
3.ai和aj的小者继续往里面递进
时间复杂度O(n)
int maxArea(int* height, int heightSize) {
if(NULL==height)
return ;
int i=,j=heightSize-;
int area,t_max=;
while(i<j){
area=(j-i)*(height[i]>height[j]?height[j]:height[i]);//计算当前面积
t_max=(t_max>area?t_max:area); //刷新最大面积
if(height[i]<height[j]) //判断需要变化的指针
i++;
else
j--;
}
return t_max;
}
Python:
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
i,j = 0,len(height)-1
vol = 0
while i<j:
vol = max(vol,(j-i)*min(height[i],height[j]))
if height[i]>height[j]:
j -= 1
else:
i += 1
return vol
【LeetCode two_pointer】11. Container With Most Water的更多相关文章
-
LeetCode Array Medium 11. Container With Most Water
Description Given n non-negative integers a1, a2, ..., an , where each represents a point at coordin ...
-
【LeetCode】11. Container With Most Water 盛最多水的容器
作者: 负雪明烛 id: fuxuemingzhu 个人博客:http://fuxuemingzhu.cn/ 个人公众号:负雪明烛 本文关键词:盛水,容器,题解,leetcode, 力扣,python ...
-
【LeetCode】11. Container With Most Water
题目: Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, a ...
-
leetcode个人题解——#11 Container with most water
class Solution { public: int maxArea(vector<int>& height) { ; ; ; while(l < r) { int h ...
-
【LeetCode 229】Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorit ...
-
【LeetCode练习题】Permutation Sequence
Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and ...
-
【LeetCode题解】二叉树的遍历
我准备开始一个新系列[LeetCode题解],用来记录刷LeetCode题,顺便复习一下数据结构与算法. 1. 二叉树 二叉树(binary tree)是一种极为普遍的数据结构,树的每一个节点最多只有 ...
-
【LeetCode题解】136_只出现一次的数字
目录 [LeetCode题解]136_只出现一次的数字 描述 方法一:列表操作 思路 Java 实现 Python 实现 方法二:哈希表 思路 Java 实现 Python 实现 方法三:数学运算 思 ...
-
【LeetCode题解】7_反转整数
目录 [LeetCode题解]7_反转整数 描述 方法一 思路 Java 实现 类似的 Java 实现 Python 实现 方法二:转化为求字符串的倒序 Java 实现 Python 实现 [Leet ...
随机推荐
-
TFS源代码管理原则
1.工作开始初次打开解决方案是应向服务器请求更新代码.2.工作结束时,应向服务器签入最新代码,并保证解决方案能够编译通过.3.不要长时间签出项目或解决方案,当向项目添加新项目后为编辑任何程序代码时,应 ...
-
ArcPy之Python介绍
1.Python简介 Python是一种面向对象.解释型计算机程序设计语言;Python是一种简单易学,功能强大的编程语言.它有高效率的高层数据结构,简单而有效地实现面向对象编程.Python简洁的语 ...
-
TYVJ1427 小白逛公园
时间: 1000ms / 空间: 131072KiB / Java类名: Main 描述 小新经常陪小白去公园玩,也就是所谓的遛狗啦…在小新家附近有一条“公园路”,路的一边从南到北依次排着n个 ...
-
批量清除.svn 或 _svn
Windows Registry Editor Version 5.00[HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Folder\shell\DeleteSVN]@=&q ...
-
HDU4519
一种比较挫的写法 /* 模拟 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #include ...
-
Vijos_1218_数字游戏_(划分型动态规划+环状动态规划)
描述 https://vijos.org/p/1218 给出n个数围成一个环,将其划分成k个部分,每个部分求和再对10取模,最后将每个部分的值相乘,求其最大值与最小值. 描述 丁丁最近沉迷于一个数字游 ...
-
nginx 源码安装
安装环境: 操作系统:Ubuntu 12.04 Nginx: V1.4.2 PCRE: V8.33 zlib: V1.2.8 下载上述源包到当前用户主目录(本机:/hom ...
-
linux iptable 设置实践
下面是设置网络时的基本状况: 主机3个网卡: eth0 192.168.0.1/24 内网 eth1 192.168.20.1/24 外网 eth2 192.168.50.1/24 会议室网络 ...
-
H3C交换机配置vlan
一,内存二,硬盘(分区,数据量大小)三,电源线,网络线四,raid(raid0,raid1,raid5)五,装系统(系统版本,分区)六,配置网络 1.创建用户 system-view #进入配置loc ...
-
举例说明Unicode 和UTF-8之间的转换
1)写这篇博客的原因 首先我要感谢这篇博客,卡了很久,看完下面这篇博客终于明白Unicode怎么转换成UTF-8了. https://blog.csdn.net/qq_32252957/article ...