【LeetCode】【Python解读】Container with most water

【LeetCode】【Python解读】Container with most water

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

这个问题是芭芭拉在采访中遇到的,不幸的是,的复杂性O(n2)该,太失望了,难怪没有通过面试。

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.

题目说的有点复杂,大意是利用x轴作底,两个随意的竖直线段作杯壁,何时盛水最多。

木桶原理大家肯定都知道,水盛多少取决于最短的杯壁,所以此题还能够引申为往围成的区域内放矩形。如何使得矩形面积最大。

题目中的不能倾斜(slant:倾斜,倾倒)相应为矩形必须水平放置。

复杂度为O(n)的思想是贪心原理,先从底边最大的情况考虑,计算最大面积后。此时要将底边长度减1,仅仅须要将杯壁较短的那一边移动一个单位距离,得到的解必然优于杯壁较长那边移动的情况。这样保证每次移动都得到的是局部最优解。

class Solution {
public:
    int maxArea(vector<int> &height) {
        int Len = height.size(),low=0,high=Len-1;
        int maxV = 0;
        while(low<high){
            maxV = max(maxV,(high-low)*min(height[low],height[high]));
            if (height[low]<height[high]) low++;
            else high--;
        }
        return maxV;
    }
};

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117528.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 【NOIP2012提高组】国王游戏[通俗易懂]

    【NOIP2012提高组】国王游戏[通俗易懂]题目描述恰逢H国国庆,国王邀请n位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这n位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。国王不希望某一个大臣获得特别多…

  • eclipse .class文件中文乱码_svn中文乱码

    eclipse .class文件中文乱码_svn中文乱码eclipse默认编码格式为GBK将其更改为utf-8即可更改后

  • PHP error_reporting() 错误控制函数功能详解

    PHP error_reporting() 错误控制函数功能详解

  • 后盾人教程_最专业的后盾

    后盾人教程_最专业的后盾CSS3系列课程开课了,老铁快上车吧一引用CSS差别link标签:外部style标签:内联style属性:嵌入式注释:/**/结尾:分号,不能省略css导入其他css样式:@i

  • 股票软件c++源代码

    股票软件c++源代码源码的部分配套开发文档http://item.taobao.com/auction/item_detail-0db1-4c3ffde99155fe1747132008fd2ece42.htm

  • Ubuntu16.04安装_vs安装路径

    Ubuntu16.04安装_vs安装路径TableofContents一、前言二、安装过程1、下载VSCode2、安装过程3、下载C++模块4、汉化5、常用快捷键一、前言因为要用到在ubuntu系统中使用VSCode来编写C++代码,在此分享VSCode的安装过程。之前我们讲了如何制作U盘启动盘,如何安装双系统,如何安装谷歌浏览器等,如果不了解的同学请看我的分类[操作系统]:操…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号