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

【Hot100算法刷题集】双指针-02-盛水最多的容器(含暴力枚举、双指针法及其合理性证明)

在这里插入图片描述

🏠关于专栏:专栏用于记录LeetCode中Hot100专题的所有题目
🎯每日努力一点点,技术变化看得见

题目转载

题目描述

🔒link->题目跳转链接
给定一个长度为 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

题目提示

● n == height.length
2 2 2 <= n <= 1 0 5 10^5 105
0 0 0 <= height[i] <= 1 0 4 10^4 104

解题思路及代码

暴力枚举法

既然要求两条线构成的最大容积,那就计算这些线两两构成的容积大小,以得到最大的容积。这个方法只需要两层for循环即可,算法复杂度为 O ( N 2 ) O(N^2) O(N2)。但这个算法的时间复杂度过高,最终会导致超时。

💡tips:这里计算容积时,使用的是高度×底部宽度。容器的高度取决于所有高度中较小的那一个。

class Solution {
public:int maxArea(vector<int>& height) {int maxCap = 0;for(int i = 0; i < height.size(); i++){for(int j = i + 1; j < height.size(); j++){int capacity = min(height[i], height[j]) * (j - i);maxCap = max(maxCap, capacity);}}return maxCap;}
};

双指针法

若定义两个变量left=0,right=height.size()-1,则可以得到由最左和最右两条线所构成的容积,即min(height[left], height[right]) * (right - left)。不管是left或right向内移动一格,宽度均会变小,故此时应当让height[left]和height[right]中小的那一个向内移动,因为宽度减小需要高度增加来补充;而当前高度受限于height[left]和height[right]中小的那一个,若小的线不发生改变,而缩小宽度,则容积只会变小;故每次只要将小的那一边向内移动即可。

下面通过示例1:[1,8,6,2,5,4,8,3,7]执行过程图,演示上述算法描述:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {
public:int maxArea(vector<int>& height) {int maxCap = 0;int left = 0, right = height.size() - 1;while(left < right){int capacity = min(height[left], height[right]) * (right - left);maxCap = max(maxCap, capacity);if(height[left] > height[right]) --right;else ++left;}return maxCap;}
};

刷题使我快乐😭
文章如有错误,请私信或在下方留言😀

相关文章:

【Hot100算法刷题集】双指针-02-盛水最多的容器(含暴力枚举、双指针法及其合理性证明)

&#x1f3e0;关于专栏&#xff1a;专栏用于记录LeetCode中Hot100专题的所有题目 &#x1f3af;每日努力一点点&#xff0c;技术变化看得见 题目转载 题目描述 &#x1f512;link->题目跳转链接 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的…...

Spring和Spring FrameWork有什么关系?两者是同一个东西吗?

Spring和Spring Framework之间的关系可以归结为以下几点&#xff1a; 广义与狭义的理解 广义上的Spring&#xff1a; 广义上的Spring泛指以Spring Framework为基础的整个Spring技术栈。Spring已经发展成为一个由多个不同子项目&#xff08;模块&#xff09;组成的成熟技术体系…...

windows10 python 解决鼠标右键菜单中没有Edit with IDLE(不使用注册表编辑器)

随便选择一个py文件&#xff0c;右击打开属性。 打开方式&#xff1a;点击更改。 最下面&#xff1a;点击更多应用&#xff0c;点击在这台电脑上查找应用 搜索找到你自己按照的python路径下 Python39\Lib\idlelib\idle.bat 文件 点击打开&#xff0c;结束。...

一些深度学习相关指令

// 服务器上查看所有的环境版本 conda env list// 删除某一个环境 conda remove -n 环境名 --all终端输入命令&#xff1a;nvidia-smi&#xff0c;可以看显卡的使用情况指定使用哪张显卡&#xff1a; os.environ["CUDA_VISIBLE_DEVICES"] 2查看服务器的cuda版本&am…...

Python 实现自动配置华为交换机

Python 实现自动配置华为交换机 在网络运维中&#xff0c;配置交换机是非常重要的一步。如果我们可以使用 Python 来实现配置交换机&#xff0c;那么我们的工作效率将会大大提高。在本文中&#xff0c;我们将学习如何使用 Python 配置华为交换机。 背景知识 华为交换机是一种…...

上海亚商投顾:沪指探底回升 华为产业链午后爆发

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 沪指昨日探底回升&#xff0c;深成指、创业板指盘中跌逾1%&#xff0c;午后集体拉升翻红。华为产业链午后走强…...

回归预测 | MATLAB实现PSO-LSTM(粒子群优化长短期记忆神经网络)多输入单输出

回归预测 | MATLAB实现PSO-LSTM(粒子群优化长短期记忆神经网络)多输入单输出 目录 回归预测 | MATLAB实现PSO-LSTM(粒子群优化长短期记忆神经网络)多输入单输出预测效果基本介绍模型介绍PSO模型LSTM模型PSO-LSTM模型程序设计参考资料致谢预测效果 Matlab实现PSO-LSTM多变量回归…...

Linux seq命令

参考资料 知っておくとちょっと便利&#xff01;seq コマンドの使い方をご紹介 目录 一. 基本语法二. 选项2.1 -f 格式化输出2.2 -s 指定分隔符2.3 -w 输出数字补齐宽度 三. 小案例3.1 递减序列3.2 批量创建测试文件3.3 批量下载文件 一. 基本语法 seq [OPTION] 结束值 seq […...

黑龙江等保测评:保障数据安全的最佳选择,助力企业无忧发展!

在数字化时代&#xff0c;数据安全已成为企业发展的重中之重。尤其是在黑龙江&#xff0c;随着信息技术的快速发展&#xff0c;数据泄露和网络攻击的风险日益增加。为了帮助企业提升数据安全防护能力&#xff0c;黑龙江等保测评应运而生&#xff0c;成为保障数据安全的有力工具…...

基于OpenCV和ROS节点的智能家居服务机器人设计流程

一、项目概述 1.1 项目目标和用途 智能家居助手项目旨在开发一款高效、智能的服务机器人&#xff0c;能够在家庭环境中执行多种任务&#xff0c;如送餐、清洁和监控。该机器人将通过自主导航、任务调度和环境感知能力&#xff0c;提升家庭生活的便利性和安全性。项目的最终目…...

vue中reduce属性的使用@3@

1.reduce方法 ​ reduce方法的使用&#xff08;数组方法&#xff09;&#xff1a; 遍历数组&#xff0c;求和 ​ 语法&#xff1a;数组名.reduce((pre,current) > {},参数2) ​ pre:上次执行该方法的返回值 ​ current&#xff1a;数据项 ​ 实例代码&#xff1a; let…...

【MySQL】索引的使用与调优技巧

为什么MySQL的MyISAM和InnoDB存储引擎索引底层选择B树&#xff0c;而不是B树&#xff1f;哈希索引&#xff1a;具体项目实践步骤&#xff1a; 为什么MySQL的MyISAM和InnoDB存储引擎索引底层选择B树&#xff0c;而不是B树&#xff1f; 对于B树&#xff1a; 索引数据内容分散在不…...

C++库之一:Loki

Loki 是一个轻量级的 C 模板库&#xff0c;旨在为高性能和灵活的 C 编程提供强大的设计模式和技术。它最初由 Andrei Alexandrescu 在他的著作《Modern C Design: Generic Programming and Design Patterns Applied》一书中介绍。 Loki 的核心特点 Loki 库的设计是为了支持复…...

前后端时间转换的那些常见问题及处理方法

在现代的Web开发中&#xff0c;前后端分离的架构已经成为主流&#xff0c;尤其是在Spring Boot和Vue.js的组合中。开发者在这种架构下经常遇到的一个问题就是如何处理时间的转换和显示。前端和后端对时间的处理方式不同&#xff0c;可能会导致时间在传递过程中出现问题&#xf…...

怎么利用XML发送物流快递通知短信

现如今短信平台越来越普遍了&#xff0c;而短信通知也分很多种&#xff0c;例如服务通知、订单通知、交易短信通知、会议通知等。而短信平台在物流行业通知这一块作用也很大。在家时:我们平时快递到了&#xff0c;如果电话联系不到本人&#xff0c;就会放到代收点&#xff0c;然…...

什么是CPU、GPU、NPU?(包懂+会)

目录 举例子 CPU&#xff1a;主厨 GPU&#xff1a;大量的厨房助理 NPU&#xff1a;面包机 总结 讲理论 CPU&#xff08;中央处理器&#xff09; GPU&#xff08;图形处理单元&#xff09; NPU&#xff08;神经网络处理单元&#xff09; 对比分析 举例子 CPU&#xff…...

TypeScript接口

接口 在编程中&#xff0c;接口是一种编程规范&#xff0c;它定义了行为和动作规范&#xff0c;接口起到了规范的作用&#xff0c;比如长方形必须要有长和宽&#xff0c;至于是多少不管&#xff0c;但是必须要有&#xff0c; 接口不关心实现的细节是什么。 interface vs type…...

Java | Leetcode Java题解之第397题整数替换

题目&#xff1a; 题解&#xff1a; class Solution {public int integerReplacement(int n) {int ans 0;while (n ! 1) {if (n % 2 0) {ans;n / 2;} else if (n % 4 1) {ans 2;n / 2;} else {if (n 3) {ans 2;n 1;} else {ans 2;n n / 2 1;}}}return ans;} }...

MySQL的 where 1=1会不会影响性能

MySQL的 where 11会不会影响性能&#xff1f; 一、引言 在编写SQL语句时&#xff0c;我们经常会遇到需要动态拼接查询条件的情况&#xff0c;尤其是在使用MyBatis这类ORM框架时。为了简化代码&#xff0c;很多开发者会使用where 11来开始他们的查询语句&#xff0c;然后通过程…...

工业连接器 如何有效提高自动化生产?

随着工业4.0的推进&#xff0c;生产自动化已经成为现代制造业的重要趋势。在这一过程中&#xff0c;工业连接器作为电气系统的关键组件&#xff0c;扮演着至关重要的角色。工业连接器不仅确保了设备间的稳定连接&#xff0c;而且在提高生产效率、保障系统可靠性以及支持设备间的…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...