当前位置: 首页 > 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;旨…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

Robots.txt 文件

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

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...