【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)


相关推荐

  • 经典手眼标定算法之Tsai-Lenz的OpenCV实现

    经典手眼标定算法之Tsai-Lenz的OpenCV实现本文主要是讲解经典手眼标定问题中的TSAI-LENZ文献方法,参考文献为“ANewTechniqueforFullyAutonomousandEfficient3DRoboticsHand/EyeCalibration”,并且实现了基于OpenCV的C++代码程序,code可去CSDN资源下载。

  • 时滞模型的matlab编程_如何用matlab仿真

    时滞模型的matlab编程_如何用matlab仿真Matlab仿真含时滞多智体一致性分析,附代码Matlab仿真含时滞多智体一致性分析,附代码Matlab仿真含时滞多智体一致性分析,附代码系统结构如下图所示:clear;clc;%2014_多智能体网络的一致性问题研究_纪良浩%此为Paper中的示例代码%例2.1:A=[0,0,0.1,0,0;0.1,0,0,0,0;0,0.15,0,0…

  • java环境_Java 开发环境配置

    java环境_Java 开发环境配置Java开发环境配置在本章节中我们将为大家介绍如何搭建Java开发环境。window系统安装java下载JDK在下载页面中你需要选择接受许可,并根据自己的系统选择对应的版本,本文以Window64位系统为例:下载后JDK的安装根据提示进行,还有安装JDK的时候也会安装JRE,一并安装就可以了。安装JDK,安装过程中可以自定义安装目录等信息,例如我们选择安装目录为C:\ProgramFil…

  • java localdatetime转date_java编码格式转换

    java localdatetime转date_java编码格式转换上篇文章介绍了Java8和Java8之前的时间处理的相关类,但是在日常开发中难免会遇到Java8和之前的旧对象互转的需求。我整理了一下之前的内容,做了一个工具类,如下:publicclassDateUtils{/***@Author:zhuoli*@Description:判断unix当前unix时间是否为0点*@paramu…

  • Spring Batch事务处理

    Spring Batch事务处理之前一直对SpringBatch的使用有些迷糊,尤其是事务这块,经常出些莫名其妙的问题,仔细了解了一下,做个小总结

  • org.postgresql.util.PSQLException: Connection to localhost:5432 refused. Check that the hostname and

    org.postgresql.util.PSQLException: Connection to localhost:5432 refused. Check that the hostname and项目启动报错org.postgresql.util.PSQLException:Connectiontolocalhost:5432refused.CheckthatthehostnameandportarecorrectandthatthepostmasterisacceptingTCP/IPconnections.解决:swin+R打开命令框…

发表回复

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

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