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

LeetCode:盛最多水的容器

文章收录于LeetCode专栏


盛最多水的容器

  给你n个非负整数a1,a2,…,an,每个数代表坐标中的一个点(i, ai) 。在坐标内画 n 条垂直线,垂直线i的两个端点分别为(i, ai) 和 (i, 0)。找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。

  说明:你不能倾斜容器。

在这里插入图片描述
  示例 1:

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

解题

1、审题

  数组中各个元素表示柱子的高度(坐标系中的纵坐标),这里的高度就可以作为容器的高,两跟柱子之间的间距就作为容器的长,即容器最多容纳水就是高乘以长。要把柱子的高作为容器的高,就会必须得取二则的相对矮的那一根柱子。例如1和8之间就得取1。

2、列出所有解

  通过对题意的理解可以使用暴力法和左右收敛法来解答改题目。

解法一(暴力法)
class Solution{public int maxArea(int[] height){int max = 0;for(int i=0; i<height.length-1; i++){for(int j=i+1; j<height.length; j++){int area = Math.min(height[i], height[j]) * (j-i);max = Math.max(max, area);}}return max;}
}
解法二(左右收敛)
class Solution{public int maxArea(int[] height){int max = 0;for(int i=0, j=height.length-1; i<j;){int h = height[i] < height[j] ? height[i++]:height[j--];int area = h * (j-i+1);max = Math.max(max, area);}return max;}
}

3、复杂度分析

  首先来看下暴力解法的时间复杂度和空间复杂度,因为暴力法使用了两层循环,所以时间复杂度为O(n2),没有使用任何额外空间,所以空间复杂度为O(1)。左右收敛法因为只使用一层循环,所以时间复杂度为O(n),同样空间复杂度为O(1)。综上左右收敛法是最优解。


一键三连,让我的信心像气球一样膨胀!

相关文章:

LeetCode:盛最多水的容器

文章收录于LeetCode专栏 盛最多水的容器 给你n个非负整数a1&#xff0c;a2&#xff0c;…&#xff0c;an&#xff0c;每个数代表坐标中的一个点(i, ai) 。在坐标内画 n 条垂直线&#xff0c;垂直线i的两个端点分别为(i, ai) 和 (i, 0)。找出其中的两条线&#xff0c;使得它们与…...

阿里云 OSS桶对象存储攻防

目录 Bucket权限配置错误-公开访问 Bucket桶爆破 特定的Bucket策略配置 Bucket Object遍历...

外网禅道配置

exportfs -avrf 修改代码&#xff0c;避免启动太慢&#xff1a;vi /opt/zbox/bin/zbox.php 启动和停止 /opt/zbox/zbox start /opt/zbox/zbox stop...

MM模块学习一(供应商创建,物料类型的定义及功能)

物料管理流程&#xff1a; 源头&#xff1a;采购需求->采购申请 MRP&#xff1a;物料需求计划。运行物料需求计划的结果&#xff0c;根据物料的性质来判断是外购&#xff08;采购申请&#xff09;或者是生产&#xff08;计划订单->生产订单&#xff09;。 采购申请&am…...

玩comfyui踩过的坑之使用ComfyUI_Custom_NODES_ALEKPET翻译组件问题

环境&#xff1a; 秋叶安装包&#xff0c;安装ComfyUI_Custom_NODES_ALEKPET组件或者直接下载网盘中的包&#xff0c;直接解压包到comfyui根目录/custom_nodes/&#xff0c;重启后&#xff0c;按指导文件操作。 注意&#xff1a;网盘指导包中有配置好的流程json文件&#xff0…...

(类)偏特化Partial Specialization

当编写一个模板特化&#xff0c;涉及部分但不是全部模板参数时&#xff0c;它被称为偏特化&#xff08;Partial Specialization&#xff09;。【注意&#xff0c;偏特化是针对类模板而言&#xff0c;函数模板不可偏特化&#xff0c;只能全特化】 偏特化是C模板编程中的一种技术…...

TypeScript 基础学习笔记:interface 与 type 的异同

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 TypeScript 学习笔记&#xff1a;interface 与 type 的异同&#x1f3a3; 引言&#x1f680; 快速入门1️⃣ Interface&#xff08;接口&#xff09;&#x1f4cb; 定义&#x1f91d; 实现&#x1f4a1; 特点 2️⃣ Type Al…...

【管理咨询宝藏95】SRM采购平台建设内部培训方案

本报告首发于公号“管理咨询宝藏”&#xff0c;如需阅读完整版报告内容&#xff0c;请查阅公号“管理咨询宝藏”。 【管理咨询宝藏95】SRM采购平台建设内部培训方案 【格式】PDF版本 【关键词】SRM采购、制造型企业转型、数字化转型 【核心观点】 - 重点是建设一个适应战略采…...

第七届机电、机器人与自动化国际会议(ICMRA 2024)即将召开!

第七届机电、机器人与自动化国际会议&#xff08;ICMRA 2024&#xff09;将于2024年9月20日-22日在中国武汉举行。ICMRA 2024为各国专家学者提供一个学术交流的平台&#xff0c;讨论机电、机器人和自动化领域的最新研究成果和未来的研究方向&#xff0c;旨在能够建立起国家间&a…...

【智能楼宇秘籍】一网关多协议无缝对接BACnet+OPC+MQTT

在繁华的都市中心&#xff0c;一座崭新的大型商业综合体拔地而起&#xff0c;集购物、餐饮、娱乐、办公于一体&#xff0c;是现代城市生活的缩影。然而&#xff0c;这座综合体的幕后英雄——一套高度集成的楼宇自动化系统&#xff0c;正是依靠多功能协议网关&#xff0c;实现了…...

leetCode68. 文本左右对齐

基本思路&#xff1a; leetCode68. 文本左右对齐 代码 class Solution { public:vector<string> fullJustify(vector<string>& words, int maxWidth) {vector<string> res;for(int i 0; i < words.size(); i){ // 枚举有多少个单词int j i 1; //…...

搜狗输入法 PC端 v14.4.0.9307 去广告绿化版.

软件介绍 搜狗拼音输入法作为众多用户计算机配置的必备工具&#xff0c;其功能的全面性已为众所周知&#xff0c;并且以其高效便捷的输入体验受到广大使用者的青睐。然而&#xff0c;该软件在提供便利的同时&#xff0c;其内置的广告元素常常为用户带来一定的干扰。为此&#…...

【汇总】虚拟机网络不通(Xshell无法连接虚拟机)排查方法

搜索关键字关键字关键字&#xff1a;虚拟机虚拟机虚拟机连接失败、虚拟机无法连接、Xshell连接失败、ping baidu.com失败、静态IP设置 Kali、CentOS、远程连接 描述&#xff1a;物理机无法连接虚拟机&#xff1b;虚拟机无法访问百度&#xff0c;虚拟机无法访问baidu.com 虚拟机…...

C++开发基础之函数参数传递的几种类型

一、前言 在C中&#xff0c;接口指针或类对象的函数参数传递是一个常见的做法&#xff0c;特别是在需要支持多态或动态绑定时。这里将介绍如何传递接口指针或类对象作为函数参数。 二、函数参数传递的几种类型 抽象类&#xff08;接口&#xff09;的实例只能通过指针或引用传…...

使用memcache 和 redis 、 实现session 会话复制和保持

一、NoSQL介绍 NoSQL是对Not Only SQL、非传统关系型数据库的统称 NoSQL一词诞生于1998年&#xff0c;2009年这个词汇再次提出指非关系型、分布式、不提供ACID的数据库设计模式 随着互联网时代的数据爆发时增长、数据库技术发展的日新月异&#xff0c;要适应新的业务需求&am…...

Tomcat 优化

在目前流行的互联网架构中&#xff0c;Tomcat在目前的网络编程中是举足轻重的&#xff0c;由于Tomcat的运行依赖于JVM&#xff0c;从虚拟机的角度把Tomcat的调整分为外部环境调优 JVM 和 Tomcat 自身调优两部分。 一、JVM组成 1. JVM 组成 JVM组成部分 类加载子系统: 使用Ja…...

如何将pdf文件换成3d模型?---模大狮模型网

PDF文件是一种广泛用于文档传输和共享的格式&#xff0c;但在某些情况下&#xff0c;我们可能希望将其中的内容转换为更具交互性和视觉效果的3D模型。本文将介绍如何将PDF文件转换为3D模型&#xff0c;为您展示实现这一想象的步骤。 选择合适的PDF文件&#xff1a; 首先&#…...

Docker 中快速构建 Redis Cluster 集群

Docker 中快速构建 Redis Cluster 集群 目录 前言环境准备 所需软件配置网络 构建 Redis Cluster 镜像 创建自定义 Dockerfile构建镜像 启动 Redis 节点容器 启动命令 配置 Redis Cluster 集群 创建 Redis 集群验证集群状态 总结 前言 Redis 是一个高性能的键值对数据库&am…...

C语言----杨辉三角

各位看官们好。学习到这里想必大家应该对C语言的了解也是很深刻的了吧。但是我们也不能忘记我们一起学习的知识啊。在我们以前学习C语言的时候我想大家应该都听说过杨辉三角吧。虽然我们把其中的规律找到那么这个代码就简单很多了。那么接下里我们就来讲讲杨辉三角。 首先我们先…...

FlaUI

FlaUI是一个基于微软UIAutomation技术&#xff08;简称UIA&#xff09;的.NET库&#xff0c;它主要用于对Windows应用程序&#xff08;如Win32、WinForms、WPF、Store Apps等&#xff09;进行自动化UI测试。FlaUI的前身是TestStack.White&#xff0c;由Roemer开发&#xff0c;旨…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...