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 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明:你不能倾斜容器。…...
《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)是一种流行的语言模型预训练范式,在nlp领域取得了巨大的成功。然而,它对视觉Transformer (ViT)的潜力尚未得到充分开发。为在视觉领域延续MLM的成功,故而探索掩码图像建模(MIM),以训练更好的视觉transforme…...
Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法
Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法 文章目录 Yolo V5在实时视频流中的建筑物与彩钢房检测:性能评估与改进方法概述Yolo V5模型概述建筑物与彩钢房检测的挑战实时视频流处理流程模型性能评估改进方法实验与分析结论与展望 概…...
图——最小生成树实现(Kruskal算法,prime算法)
目录 预备知识: 最小生成树概念: Kruskal算法: 代码实现如下: 测试: Prime算法 : 代码实现如下: 测试: 结语: 预备知识: 连通图:在无向图…...
Unity3D xLua开发环境搭建详解
前言 xLua是一种基于Lua语言的开发框架,可以帮助开发者在Unity3D中使用Lua脚本来开发游戏。 对惹,这里有一个游戏开发交流小组,希望大家可以点击进来一起交流一下开发经验呀! 在本文中,我们将详细介绍如何搭建Unity…...
Python笔记-super().init(root)的作用
假设我们有一个名为Animal的父类,它有一个属性color,在其构造函数__init__中被初始化: class Animal:def __init__(self, color):self.color color现在,我们想创建一个Animal的子类,名为Dog。Dog类有自己的属性name&…...
【git 使用】使用 git rebase -i 修改任意的提交信息/合并多个提交
修改最近一次的提交信息的方法有很多,可以参考这篇文章,但是对于之前的提交信息进行修改只能使用 rebase。 修改提交信息 假设我们想修改下面这个提交信息,想把【登录】改成【退出登录】步骤如下 运行 git rebase -i head~3 打开了一个文本…...
【Vue3】toRefs和toRef在reactive中的一些应用
💗💗💗欢迎来到我的博客,你将找到有关如何使用技术解决问题的文章,也会找到某个技术的学习路线。无论你是何种职业,我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章,也欢…...
力扣精选算法100道——Z字形变换(模拟专题)
目录 🎈了解题意 🎈算法原理 🚩先处理第一行和最后一行 🚩再处理中间行 🎈实现代码 🎈了解题意 大家看到这个题目的时候肯定是很迷茫的,包括我自己也是搞不清楚题目什么意思,我…...
Elastic Stack--01--简介、安装
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1. Elastic Stack 简介为什么要学习ESDB-Engines搜索引擎类数据库排名常年霸榜func main() {listen, err : net.Listen(&quo…...
[java基础揉碎]this
引出this: 什么是this: java虚拟机会给每个对象分配 this,代表当前对象。 这里的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 注:-m表示权限,类chmod命令 4、执行命令启动…...
服务器防火墙的应用技术有哪些类型?
随着互联网的发展,网络安全问题更加严峻。服务器防火墙技术作为一种基础的网络安全技术,对于保障我们的网络安全至关重要。本文将介绍服务器防火墙的概念和作用,以及主要的服务器防火墙技术,包括数据包过滤、状态检测、代理服务、…...
IP地理位置查询定位:技术原理与实际应用
在互联网时代,IP地址是连接世界的桥梁,而了解IP地址的地理位置对于网络管理、个性化服务以及安全监控都至关重要。IP数据云将深入探讨IP地理位置查询定位的技术原理、实际应用场景以及相关的隐私保护问题,旨在为读者提供全面了解和应用该技术…...
当人脸识别‘脸盲’时:ReID如何靠‘衣着体态’在安防、零售中找人?
当人脸识别失效时:ReID技术如何通过衣着体态实现精准追踪 在智慧城市建设和零售数字化转型的浪潮中,视频分析技术正面临一个尴尬的现实困境——当人脸识别因遮挡、远距离或背对摄像头等原因失效时,如何继续追踪目标人物?这个问题…...
NEURAL MASK 模型调试技巧:使用IDE进行Python代码跟踪与问题定位
NEURAL MASK 模型调试技巧:使用IDE进行Python代码跟踪与问题定位 调试代码,尤其是涉及复杂模型加载和推理的代码,有时候就像在黑暗的房间里找一颗掉落的螺丝钉。你大概知道它就在那儿,但就是看不见摸不着。对于NEURAL MASK这类模…...
从规格书到点亮屏幕:RK3568+GM8775C双通道LVDS调试全流程解析
RK3568GM8775C双通道LVDS屏幕调试实战:从参数解析到设备树配置 第一次拿到一块非标准LVDS屏幕时,我盯着规格书里密密麻麻的表格和数据完全无从下手。作为硬件工程师,我们常常需要面对各种定制化显示屏的驱动问题。本文将带你深入理解如何从屏…...
Qwen3-0.6B-FP8效果对比:与Phi-3-mini、Gemma-2B在低资源设备上的实测PK
Qwen3-0.6B-FP8效果对比:与Phi-3-mini、Gemma-2B在低资源设备上的实测PK 想在小显存的电脑上跑个大模型,体验一下AI对话的乐趣,是不是总被“显存不足”的提示劝退?别急,今天我们就来一场专为“小显存”设备准备的AI模…...
GPON OMCI抓包避坑指南:Wireshark插件版本、芯片指令与实战解析全流程
GPON OMCI抓包避坑指南:Wireshark插件版本、芯片指令与实战解析全流程 在GPON网络运维和研发过程中,OMCI(ONU Management and Control Interface)协议分析是定位问题的关键手段。但许多工程师在实际操作中常陷入版本兼容性陷阱、芯…...
Qwen3-VL-4B Pro开箱体验:基于4B进阶模型,视觉理解与推理能力实测
Qwen3-VL-4B Pro开箱体验:基于4B进阶模型,视觉理解与推理能力实测 1. 项目概览:从2B到4B的视觉理解跃迁 Qwen3-VL-4B Pro是基于阿里通义千问Qwen/Qwen3-VL-4B-Instruct模型构建的视觉语言交互服务。相比广为人知的2B轻量版,这个…...
STM32一键下载电路设计与CH340应用
STM32一键下载电路设计与实现1. 项目概述1.1 功能需求STM32系列微控制器在开发过程中,通常需要通过串口进行程序下载。传统下载方式需要手动操作BOOT0和RESET引脚,过程繁琐且容易出错。本项目设计了一种基于CH340芯片的自动下载电路,通过软件…...
Blender多材质合并与Three.js统一渲染:从烘焙到GLB导出的完整指南
1. 多材质模型合并的核心痛点 在Blender中合并多个模型时,即使将它们合并为单一Mesh对象,导出为GLB格式后在Three.js中仍然会被拆分成多个Mesh。这个问题困扰过不少开发者,我自己在早期项目中也踩过这个坑。根本原因在于:Three.js…...
从零构建企业级Text2Sql应用:Vanna私有化部署与Dify工作流集成
1. 企业级Text2Sql应用的核心价值 想象一下,财务部门的同事对着Excel表格发愁:"能不能帮我找出上季度华东区销售额超过50万的所有客户?"传统做法需要找IT部门提需求,等开发人员写SQL查询,流程可能长达数三天…...
雪女-斗罗大陆-造相Z-Turbo系统管理:Ubuntu服务器运维与模型服务监控
雪女-斗罗大陆-造相Z-Turbo系统管理:Ubuntu服务器运维与模型服务监控 想让你的“雪女”模型在Ubuntu服务器上像真正的封号斗罗一样,拥有稳定、可靠、持久的战斗力吗?对于任何投入生产环境的AI服务来说,部署成功只是第一步&#x…...
