C++实现LeetCode(11.装最多水的容器)

[LeetCode] 11. Container With Most Water 装最多水的容器

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 and nis at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

这道求装最多水的容器的题和那道 Trapping Rain Water 很类似，但又有些不同，那道题让求整个能收集雨水的量，这道只是让求最大的一个的装水量，而且还有一点不同的是，那道题容器边缘不能算在里面，而这道题却可以算，相比较来说还是这道题容易一些，这里需要定义i和j两个指针分别指向数组的左右两端，然后两个指针向中间搜索，每移动一次算一个值和结果比较取较大的，容器装水量的算法是找出左右两个边缘中较小的那个乘以两边缘的距离，代码如下：

C++ 解法一：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            res = max(res, min(height[i], height[j]) * (j - i));
            height[i] < height[j] ? ++i : --j;
        }
        return res;
    }
};

Java 解法一：

public class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while (i < j) {
            res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) ++i;
            else --j;
        }
        return res;
    }
}

这里需要注意的是，由于 Java 中的三元运算符 A?B:C 必须须要有返回值，所以只能用 if..else.. 来替换，不知道 Java 对于三元运算符这么严格的限制的原因是什么。

下面这种方法是对上面的方法进行了小幅度的优化，对于相同的高度们直接移动i和j就行了，不再进行计算容量了，参见代码如下：

C++ 解法二：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            int h = min(height[i], height[j]);
            res = max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
};

Java 解法二：

public class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while (i < j) {
            int h = Math.min(height[i], height[j]);
            res = Math.max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
}

到此这篇关于C++实现LeetCode(11.装最多水的容器)的文章就介绍到这了,更多相关C++实现装最多水的容器内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(6.字型转换字符串)

    [LeetCode] 6. ZigZag Conversion 之字型转换字符串 The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P   A   H   N A P L S I I G Y  

  • C++实现LeetCode(42.收集雨水)

    C++实现LeetCode(42.收集雨水)

    [LeetCode] 42. Trapping Rain Water 收集雨水 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,

  • C++实现LeetCode(8.字符串转为整数)

    [LeetCode] 8. String to Integer (atoi) 字符串转为整数 Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this ch

  • C++实现LeetCode(验证数字)

    [LeetCode] Valid Number 验证数字 Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true "

  • C++实现LeetCode(7.翻转整数)

    [LeetCode] 7. Reverse Integer 翻转整数 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment whi

  • C++实现LeetCode(647.回文子字符串)

    [LeetCode] 647. Palindromic Substrings 回文子字符串 Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of sa

  • C++实现LeetCode(44.外卡匹配)

    [LeetCode] 44. Wildcard Matching 外卡匹配 Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequenc

  • C++实现LeetCode(10.正则表达式匹配)

    [LeetCode] 10. Regular Expression Matching 正则表达式匹配 Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. T

  • C++实现LeetCode(132.拆分回文串之二)

    [LeetCode] 132.Palindrome Partitioning II 拆分回文串之二 Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example: Input: "aab" Output: 1 Explan

  • C++实现LeetCode(11.装最多水的容器)

    C++实现LeetCode(11.装最多水的容器)

    [LeetCode] 11. Container With Most Water 装最多水的容器 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

  • JavaScript实现twitter puddles算法实例

    JavaScript实现twitter puddles算法实例

    今天发现了一个挺好玩的算法题,下面是它的算法描述,源自twitter的一道面试题. twitter puddles 算法描述 先看一副图 上图里的数字是根据一个数组内容来描述的,最后会根据每个数字的大小来模拟一道墙的高度,最后生成一面墙,问你,当下雨的时候,这面墙可以装多少水,以1为计数单位. 下面是装完水之后的一面墙的样子 看完上面上幅图,感觉是不是很好玩,确实,下面来简单的分析下它的算法实现 其实这个原理比较简单,总共有下面几个要点: 1.最左边和最右边肯定不能装水 2.装水的高度依赖自身左

  • 关于全局变量和局部变量的那些事

    变量对于学习js,学习编程语言的同学在熟悉不过了,在这里就不在阐述官方的定义了,网上太多了,今天我们就从生活中来理解他 1.什么是变量? 比如: 一个水杯里面装了水,这个水杯就是变量: 一瓶啤酒,这个啤酒瓶就是变量: 变量就是一个载体,一个媒介 2.定义变量 var a=12://typeof a=Numer var a='aaa' //typeof a =string 由此可见 变量的类型取决于给他付了什么值 例如,一个杯子,装了水就是水杯,装了酒就是酒杯,装了醋就是醋瓶 3.变量类型 变量类

  • 关于springboot-starter-undertow和tomcat的区别说明

    目录 什么是tomcat tomcat的作用 javaweb项目都需要tomcat? Java前后端分离的核心思想 springboot内置的tomcat undertow和tomcat的区别 部署jar和war包 springboot下比较tomcat与undertow性能 第一步 第二步 第三步 第四步 第五步 什么是tomcat 在说undertow和tomcat区别之前,先说下tomcat是什么(如果知道了可以跳过哦!) Tomcat:免费开源,轻量级应用服务器,在中小型系统和并发访问用

  • docker初识之五分钟认识docker

    docker初识之五分钟认识docker

    什么是docker? Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化.容器是完全使用沙箱机制,相互之间不会有任何接口. 把他想象成一个用了一种新颖方式实现的超轻量虚拟机,在大概效果上也是正确的.当然在实现的原理和应用上还是和VM有巨大差别的,并且专业的叫法是应用容器(Application Container). 为啥要用docker? 那么应用容器长什么样子呢,一个做好的应用容器长得就

  • iOS直播类APP开发流程解析

    本文为大家分享了iOS直播类APP开发流程,供大家参考,具体内容如下 一 . 音视频处理的一般流程: 数据采集→数据编码→数据传输(流媒体服务器) →解码数据→播放显示 1.数据采集: 摄像机及拾音器收集视频及音频数据,此时得到的为原始数据 涉及技术或协议: 摄像机:CCD.CMOS 拾音器:声电转换装置(咪头).音频放大电路 2.数据编码: 使用相关硬件或软件对音视频原始数据进行编码处理(数字化)及加工(如音视频混合.打包封装等),得到可用的音视频数据 涉及技术或协议: 编码方式:CBR.VB

  • STL区间成员函数及区间算法总结

    在这里总结下可替代循环的区间成员函数和区间算法: 相比单元素遍历操作,使用区间成员函数的优势在于: 1)更少的函数调用 2)更少的元素移动 3)更少的内存分配 在区间成员函数不适用的情况下也应该使用区间算法,至少,相比手写循环而言,它更加简单,有效,并且不容易出错: 区间成员函数 区间构造 标准容器都支持区间构造函数: 复制代码 代码如下: container::container(InputIterator begin, // 区间的起点                   InputIter

  • flash as Actionscript中的数组的使用方法

    如果你对数组感性趣的话,那么你也一定了解变量吧.变量是装着数据的容器,数据可以是数字.字符串或者是个布尔值. 数组与变量相似同样是做为数据的容器,但它还能包含更多的数据,每一个元素(数据中的一部分)都被附于一个索引. 数组可以用来保存你的脚本和组织结构,它们通常用来去组织一些在某些方面有些关联的数值,这些数值采用一个索引值与数组中其它的元素区分开来.你可以用下面这个方法 去定义 3个变量:: quote1="Flash is cool!" quote2="Flash is m

  • 一个牛人给Java初学者的建议(必看篇)

    一个牛人给Java初学者的建议(必看篇)

    给初学者之一:浅谈Java及应用学java 从不知java为何物到现在一个小小的j2ee项目经理虽说不上此道高手,大概也算有点斤两了吧每次上网,泡bbs逛论坛,没少去java相关的版 面总体感觉初学者多,高手少,精通的更少由于我国高等教育制度教材陈旧,加上java自身发展不过十年左右的时间还有一个很重要的原因就是java这门语 言更适合商业应用所以高校里大部分博士老师们对此语言的了解甚至不比本科生多在这种环境下,很多人对java感到茫然,不知所措,不懂java能做什么即 便知道了java很有用,

  • Android开发中的Surface库及用其制作播放器UI的例子

    Android开发中的Surface库及用其制作播放器UI的例子

    1.Surface 1.1. 就如在C语言编程一样,通过一个文件的句柄,就可以操作文件,获取文件的内容. 同样的,通过Surface就可以获取raw buffer其中的内容.原生缓冲区(raw buffer)存储着当前窗口的像素数据. 1.2.事实上,当得到一个Surface对象时,同时会得到一个Canvas(画布)对象.这一点可以通过查看\frameworks\base\core\java\android\view\Surface.java文件可知道Surface类定义了一个Canvas成员变

随机推荐