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地理位置查询定位的技术原理、实际应用场景以及相关的隐私保护问题,旨在为读者提供全面了解和应用该技术…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...
6.计算机网络核心知识点精要手册
计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法:数据与控制信息的结构或格式,如同语言中的语法规则语义:控制信息的具体含义和响应方式,规定通信双方"说什么"同步:事件执行的顺序与时序…...
基于谷歌ADK的 智能产品推荐系统(2): 模块功能详解
在我的上一篇博客:基于谷歌ADK的 智能产品推荐系统(1): 功能简介-CSDN博客 中我们介绍了个性化购物 Agent 项目,该项目展示了一个强大的框架,旨在模拟和实现在线购物环境中的智能导购。它不仅仅是一个简单的聊天机器人,更是一个集…...
window 显示驱动开发-如何查询视频处理功能(三)
D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针,该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...
EC2安装WebRTC sdk-c环境、构建、编译
1、登录新的ec2实例,证书可以跟之前的实例用一个: ssh -v -i ~/Documents/cert/qa.pem ec2-user70.xxx.165.xxx 2、按照sdk-c demo中readme的描述开始安装环境: https://github.com/awslabs/amazon-kinesis-video-streams-webrtc-sdk-c 2…...
MySQL 数据库深度剖析:事务、SQL 优化、索引与 Buffer Pool
在当今数据驱动的时代,数据库作为数据存储与管理的核心,其性能与可靠性至关重要。MySQL 作为一款广泛使用的开源数据库,在众多应用场景中发挥着关键作用。在这篇博客中,我将围绕 MySQL 数据库的核心知识展开,涵盖事务及…...
