当前位置: 首页 > news >正文

Leetcode 11.盛水最多的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

 思路

题目给定一个数组让求最大容量,有以下两种方法

一、暴力枚举

从下标0开始把所有情况全部算出来求最大,及其原始暴力的方法,作为一个学习算法和编程的人,首先排除此方法。

二、双指针

此类型题目可以理解为日常生活中所说的木桶效应,一个木桶能装多少水是由最短的那块板子来决定的,同样在计算容积时,高是由最短的那个数来决定的,而想要从数组中找出最优解,枚举是不可缺少的,但要尽可能的控制枚举的次数,从而降低代码的时间复杂度。

用h表示高,w表示宽

从中间随机截取一段来举例,[6,2,5,4]首先可以算出体积为3*4=12,现在假设拿4依次根其他几个数作枚举,w无疑是在减小的,那么现在会出现两种情况:

但只要仔细观察就会发现无论哪种情况,总容量都是在减少的。

1.h比4小,和刚开始比h减小了w也减小了,容量无疑也减小了。

2.h比4大,那高度还得是4,所以和刚开始比h不变,w减小,容积量在减小。

所以当在一个区间内选最左和最右两个数算出容积之后,两个数中小的那个数已经完全没有必要再去向内进行枚举了,因为无论怎么枚举,容量都是变小的。此时4可以直接不考虑了。

我们可以知道,容量是受宽和高的影响的,而我们需要找出的就是一个宽和高都相对较高的值,结合上面的分析,所以为了加快效率,两个指针一个在前一个在后同时由外向内进行遍历可以大大节约时间,那边小直接向内移动那边,然后计算容量,这样就可以用O(n)的时间复杂度来找出最大容量了。

扩大到整个数组,最左最右计算完直接干掉1向右移,继续找,如果比之前算出来的都大就更新max。

题解

class Solution {
public:int maxArea(vector<int>& height) {int left=0,right=height.size()-1;int max=0,h=0,w=0;while(left<right){w=right-left;if(height[left]<height[right]) h=height[left++];else h=height[right--];if(w*h>max) max=w*h;}return max;}
};

相关文章:

Leetcode 11.盛水最多的容器

题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&#xff1a;你不能倾斜容器。…...

《Go 简易速速上手小册》第7章:包管理与模块(2024 最新版)

文章目录 7.1 使用 Go Modules 管理依赖 - 掌舵向未来7.1.1 基础知识讲解7.1.2 重点案例:Web 服务功能描述实现步骤扩展功能7.1.3 拓展案例 1:使用数据库功能描述实现步骤扩展功能7.1.4 拓展案例 2:集成 Redis 缓存功能描述实现步骤...

【论文精读】IBOT

摘要 掩码语言建模(MLM)是一种流行的语言模型预训练范式&#xff0c;在nlp领域取得了巨大的成功。然而&#xff0c;它对视觉Transformer (ViT)的潜力尚未得到充分开发。为在视觉领域延续MLM的成功&#xff0c;故而探索掩码图像建模(MIM)&#xff0c;以训练更好的视觉transforme…...

Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法

Yolo V5在实时视频流中的建筑物与彩钢房检测&#xff1a;性能评估与改进方法 文章目录 Yolo V5在实时视频流中的建筑物与彩钢房检测&#xff1a;性能评估与改进方法概述Yolo V5模型概述建筑物与彩钢房检测的挑战实时视频流处理流程模型性能评估改进方法实验与分析结论与展望 概…...

图——最小生成树实现(Kruskal算法,prime算法)

目录 预备知识&#xff1a; 最小生成树概念&#xff1a; Kruskal算法&#xff1a; 代码实现如下&#xff1a; 测试&#xff1a; Prime算法 &#xff1a; 代码实现如下&#xff1a; 测试&#xff1a; 结语&#xff1a; 预备知识&#xff1a; 连通图&#xff1a;在无向图…...

Unity3D xLua开发环境搭建详解

前言 xLua是一种基于Lua语言的开发框架&#xff0c;可以帮助开发者在Unity3D中使用Lua脚本来开发游戏。 对惹&#xff0c;这里有一个游戏开发交流小组&#xff0c;希望大家可以点击进来一起交流一下开发经验呀&#xff01; 在本文中&#xff0c;我们将详细介绍如何搭建Unity…...

Python笔记-super().init(root)的作用

假设我们有一个名为Animal的父类&#xff0c;它有一个属性color&#xff0c;在其构造函数__init__中被初始化&#xff1a; class Animal:def __init__(self, color):self.color color现在&#xff0c;我们想创建一个Animal的子类&#xff0c;名为Dog。Dog类有自己的属性name&…...

【git 使用】使用 git rebase -i 修改任意的提交信息/合并多个提交

修改最近一次的提交信息的方法有很多&#xff0c;可以参考这篇文章&#xff0c;但是对于之前的提交信息进行修改只能使用 rebase。 修改提交信息 假设我们想修改下面这个提交信息&#xff0c;想把【登录】改成【退出登录】步骤如下 运行 git rebase -i head~3 打开了一个文本…...

【Vue3】toRefs和toRef在reactive中的一些应用

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…...

力扣精选算法100道——Z字形变换(模拟专题)

目录 &#x1f388;了解题意 &#x1f388;算法原理 &#x1f6a9;先处理第一行和最后一行 &#x1f6a9;再处理中间行 &#x1f388;实现代码 &#x1f388;了解题意 大家看到这个题目的时候肯定是很迷茫的&#xff0c;包括我自己也是搞不清楚题目什么意思&#xff0c;我…...

Elastic Stack--01--简介、安装

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1. Elastic Stack 简介为什么要学习ESDB-Engines搜索引擎类数据库排名常年霸榜![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/051342a83f574c8c910cda…...

.NET项目web自动化测试实战——Selenium 2.0

&#x1f525; 交流讨论&#xff1a;欢迎加入我们一起学习&#xff01; &#x1f525; 资源分享&#xff1a;耗时200小时精选的「软件测试」资料包 &#x1f525; 教程推荐&#xff1a;火遍全网的《软件测试》教程 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1…...

【Day53】代码随想录之动态规划_买卖股票ⅠⅡ

文章目录 动态规划理论基础动规五部曲&#xff1a;出现结果不正确&#xff1a; 1. 买卖股票的最佳时机2. 买卖股票的最佳时机Ⅱ 动态规划理论基础 动规五部曲&#xff1a; 确定dp数组 下标及dp[i] 的含义。递推公式&#xff1a;比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初…...

Swift Combine 使用调试器调试管道 从入门到精通二十六

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…...

go内置库函数实现client与server数据的发送接收

功能&#xff1a;客户端持续写入数据&#xff0c;直到输入exit退出&#xff0c;服务端读取数据并打印 注意&#xff1a;server和client目录在同一层级 服务端 server/main package mainimport ("fmt""net" )func main() {listen, err : net.Listen(&quo…...

[java基础揉碎]this

引出this: 什么是this: java虚拟机会给每个对象分配 this&#xff0c;代表当前对象。 这里的this就是new出来的这个对象 this的本质: this是个引用在堆中指向它自己: this的细节: 访问成员方法: 访问构造器:...

vulnhub靶场之Deathnote

一.环境搭建 1.靶场描述 Level - easy Description : dont waste too much time thinking outside the box . It is a Straight forward box . This works better with VirtualBox rather than VMware 2.靶场下载 https://www.vulnhub.com/entry/deathnote-1,739/ 3.启动环…...

Docker安装Postgresql12

1、搜索仓库中postgres docker search postgres 2、拉取镜像 docker pull postgres docker pull postgres:12 #拉取12版本的PG库 3、创建数据库文件夹 cd /temp/ && mkdir -m 755 postgres-data 注&#xff1a;-m表示权限&#xff0c;类chmod命令 4、执行命令启动…...

服务器防火墙的应用技术有哪些类型?

随着互联网的发展&#xff0c;网络安全问题更加严峻。服务器防火墙技术作为一种基础的网络安全技术&#xff0c;对于保障我们的网络安全至关重要。本文将介绍服务器防火墙的概念和作用&#xff0c;以及主要的服务器防火墙技术&#xff0c;包括数据包过滤、状态检测、代理服务、…...

IP地理位置查询定位:技术原理与实际应用

在互联网时代&#xff0c;IP地址是连接世界的桥梁&#xff0c;而了解IP地址的地理位置对于网络管理、个性化服务以及安全监控都至关重要。IP数据云将深入探讨IP地理位置查询定位的技术原理、实际应用场景以及相关的隐私保护问题&#xff0c;旨在为读者提供全面了解和应用该技术…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...