当前位置: 首页 > 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;而且在提高生产效率、保障系统可靠性以及支持设备间的…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...