【LeetCode two_pointer】11. Container With Most Water

时间:2021-08-13 22:33:18

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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个非负值a1a2, ..., an,(iai) 和 (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的更多相关文章

  1. LeetCode Array Medium 11&period; Container With Most Water

    Description Given n non-negative integers a1, a2, ..., an , where each represents a point at coordin ...

  2. 【LeetCode】11&period; Container With Most Water 盛最多水的容器

    作者: 负雪明烛 id: fuxuemingzhu 个人博客:http://fuxuemingzhu.cn/ 个人公众号:负雪明烛 本文关键词:盛水,容器,题解,leetcode, 力扣,python ...

  3. 【LeetCode】11&period; Container With Most Water

    题目: Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, a ...

  4. leetcode个人题解——&num;11 Container with most water

    class Solution { public: int maxArea(vector<int>& height) { ; ; ; while(l < r) { int h ...

  5. 【LeetCode 229】Majority Element II

    Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorit ...

  6. 【LeetCode练习题】Permutation Sequence

    Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and ...

  7. 【LeetCode题解】二叉树的遍历

    我准备开始一个新系列[LeetCode题解],用来记录刷LeetCode题,顺便复习一下数据结构与算法. 1. 二叉树 二叉树(binary tree)是一种极为普遍的数据结构,树的每一个节点最多只有 ...

  8. 【LeetCode题解】136&lowbar;只出现一次的数字

    目录 [LeetCode题解]136_只出现一次的数字 描述 方法一:列表操作 思路 Java 实现 Python 实现 方法二:哈希表 思路 Java 实现 Python 实现 方法三:数学运算 思 ...

  9. 【LeetCode题解】7&lowbar;反转整数

    目录 [LeetCode题解]7_反转整数 描述 方法一 思路 Java 实现 类似的 Java 实现 Python 实现 方法二:转化为求字符串的倒序 Java 实现 Python 实现 [Leet ...

随机推荐

  1. TFS源代码管理原则

    1.工作开始初次打开解决方案是应向服务器请求更新代码.2.工作结束时,应向服务器签入最新代码,并保证解决方案能够编译通过.3.不要长时间签出项目或解决方案,当向项目添加新项目后为编辑任何程序代码时,应 ...

  2. ArcPy之Python介绍

    1.Python简介 Python是一种面向对象.解释型计算机程序设计语言;Python是一种简单易学,功能强大的编程语言.它有高效率的高层数据结构,简单而有效地实现面向对象编程.Python简洁的语 ...

  3. TYVJ1427 小白逛公园

    时间: 1000ms / 空间: 131072KiB / Java类名: Main 描述     小新经常陪小白去公园玩,也就是所谓的遛狗啦…在小新家附近有一条“公园路”,路的一边从南到北依次排着n个 ...

  4. 批量清除&period;svn 或 &lowbar;svn

    Windows Registry Editor Version 5.00[HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Folder\shell\DeleteSVN]@=&q ...

  5. HDU4519

    一种比较挫的写法 /* 模拟 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #include ...

  6. Vijos&lowbar;1218&lowbar;数字游戏&lowbar;&lpar;划分型动态规划&plus;环状动态规划&rpar;

    描述 https://vijos.org/p/1218 给出n个数围成一个环,将其划分成k个部分,每个部分求和再对10取模,最后将每个部分的值相乘,求其最大值与最小值. 描述 丁丁最近沉迷于一个数字游 ...

  7. nginx 源码安装

    安装环境: 操作系统:Ubuntu 12.04 Nginx:     V1.4.2 PCRE:    V8.33 zlib:         V1.2.8 下载上述源包到当前用户主目录(本机:/hom ...

  8. linux iptable 设置实践

    下面是设置网络时的基本状况: 主机3个网卡: eth0 192.168.0.1/24   内网 eth1 192.168.20.1/24  外网 eth2 192.168.50.1/24  会议室网络 ...

  9. H3C交换机配置vlan

    一,内存二,硬盘(分区,数据量大小)三,电源线,网络线四,raid(raid0,raid1,raid5)五,装系统(系统版本,分区)六,配置网络 1.创建用户 system-view #进入配置loc ...

  10. 举例说明Unicode 和UTF-8之间的转换

    1)写这篇博客的原因 首先我要感谢这篇博客,卡了很久,看完下面这篇博客终于明白Unicode怎么转换成UTF-8了. https://blog.csdn.net/qq_32252957/article ...