当前位置: 首页 > 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;旨在为读者提供全面了解和应用该技术…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...