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

力扣经典150题解析之二十八:盛最多水的容器

目录

    • 力扣经典150题解析之二十八:盛最多水的容器
      • 1. 介绍
      • 2. 问题描述
      • 3. 示例
      • 4. 解题思路
      • 5. 算法实现
      • 6. 复杂度分析
      • 7. 测试与验证
        • 测试用例设计
        • 测试结果分析
      • 8. 总结
      • 9. 参考文献
      • 感谢阅读

力扣经典150题解析之二十八:盛最多水的容器

1. 介绍

在这篇文章中,我们将解析力扣经典150题中的第二十八题:盛最多水的容器。题目要求找出能够容纳最多水的容器,即找出数组中的两条线段,使得它们与 x 轴构成的容器能够容纳最多的水。

2. 问题描述

给定一个长度为 n 的整数数组 height,数组中每个元素表示垂直线的高度。找出数组中的两个元素,使得它们构成的容器能够容纳最多的水。

3. 示例

示例 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

4. 解题思路

我们可以使用双指针法来解决这个问题:

  1. 使用两个指针 leftright 分别指向数组的开头和结尾。
  2. 计算当前指针所指向的两条线段之间能够容纳的水的容量,即 min(height[left], height[right]) * (right - left)
  3. left 指向的线段和 right 指向的线段中高度较小的那个向内移动,因为向内移动较小的线段,可能会找到更高的线段来容纳更多的水。
  4. 继续比较移动后的线段之间的水容量,更新最大水容量。
  5. 直到 leftright 相遇,遍历结束。

5. 算法实现

public int maxArea(int[] height) {int left = 0, right = height.length - 1;int maxArea = 0;while (left < right) {int h = Math.min(height[left], height[right]);int width = right - left;int area = h * width;maxArea = Math.max(maxArea, area);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
}

6. 复杂度分析

  • 时间复杂度:O(n),其中 n 是数组 height 的长度。双指针遍历一次数组。
  • 空间复杂度:O(1),只使用了常数级的额外空间。

7. 测试与验证

测试用例设计
  • 输入数组长度为2,包含两个元素。
  • 输入数组长度为3,包含三个元素。
  • 输入数组长度为9,包含多个元素。
测试结果分析

根据不同的测试用例,分析算法的输出结果,验证解决方案的正确性和有效性。

8. 总结

通过双指针法,我们可以高效地找出能够容纳最多水的容器,解决了该问题。本文详细介绍了解题思路、算法实现和复杂度分析,希望对读者理解该问题和解决方法有所帮助。

9. 参考文献

  • LeetCode 官方网站
  • 《算法导论》
  • 《程序员面试金典》

感谢阅读

期待下一篇…

相关文章:

力扣经典150题解析之二十八:盛最多水的容器

目录 力扣经典150题解析之二十八&#xff1a;盛最多水的容器1. 介绍2. 问题描述3. 示例4. 解题思路5. 算法实现6. 复杂度分析7. 测试与验证测试用例设计测试结果分析 8. 总结9. 参考文献感谢阅读 力扣经典150题解析之二十八&#xff1a;盛最多水的容器 1. 介绍 在这篇文章中&…...

Rockchip Android13 Vold(二):Framework层

目录 前言 1、接收VolumeInfo状态 2、通知VolumeInfo状态变化 3、创建StorageVolume...

Oracle数据库故障类别及日常运维规划策略

一、故障类别 1、语句故障 单个数据库操作失败&#xff08;select、insert、update或delete&#xff09;&#xff0c;如&#xff1a; 在表中输入无效的数据&#xff0c;解决方法&#xff1a;可与用户合作来验证并更正数据&#xff1b;执行操作&#xff0c;但权限不足&#x…...

电商技术揭秘九:搜索引擎中的SEO数据分析与效果评估

相关系列文章 电商技术揭秘一&#xff1a;电商架构设计与核心技术 电商技术揭秘二&#xff1a;电商平台推荐系统的实现与优化 电商技术揭秘三&#xff1a;电商平台的支付与结算系统 电商技术揭秘四&#xff1a;电商平台的物流管理系统 电商技术揭秘五&#xff1a;电商平台的个性…...

多线程传参以及线程的优缺点

进程是资源分配的基本单位 线程是调度的基本单位 笼统来说&#xff0c;线程有以下优点&#xff1a; 创建一个新线程的代价要比创建一个新进程小得多 与进程之间的切换相比&#xff0c;线程之间的切换需要操作系统做的工作要少很多 线程占用的资源要比进程少很多 能充分利用多…...

keil创建单片机工程

一、创建工程 打开Keil uVision4&#xff0c;依次选择 Project—>New uVision4 Project&#xff0c;选择工程保存路径及填写工程名称&#xff0c;如下图 然后点“保存”。在Select a CPU Data Base File中选择"STC MCU Database"&#xff0c;点 "OK"&am…...

QT 串口助手 学习制作记录

QT 串口助手qt 学习制作记录 参考教程&#xff1a;​​​​​​QT初体验&#xff1a;手把手带你写一个自己的串口助手_qt设计串口助手的流程图-CSDN博客 Qt之串口编程&#xff08;添加QSerialPort模块&#xff09;_如何安装 qt串口模块教程-CSDN博客 串口调试助手&#xff1…...

Github 2024-04-13 Rust开源项目日报Top10

根据Github Trendings的统计,今日(2024-04-13统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Rust项目10CUE项目1Go项目1Tauri: 构建小型、快速和安全的桌面应用程序 创建周期:1673 天开发语言:Rust协议类型:Apache License 2.0Star数量…...

大模型日报|今日必读的10篇大模型论文

大家好&#xff0c;今日必读的大模型论文来啦&#xff01; 1.谷歌推出新型 Transformer 架构&#xff1a;反馈注意力就是工作记忆 虽然 Transformer 给深度学习带来了革命性的变化&#xff0c;但二次注意复杂性阻碍了其处理无限长输入的能力。 谷歌研究团队提出了一种新型 T…...

深度学习 Lecture 8 决策树

一、决策树模型&#xff08;Decision Tree Model) 椭圆形代表决策节点&#xff08;decison nodes)&#xff0c;矩形节点代表叶节点&#xff08;leaf nodes)&#xff0c;方向上的值代表属性的值&#xff0c; 构建决策树的学习过程&#xff1a; 第一步&#xff1a;决定在根节点…...

打包 docker 容器镜像到另一台电脑

# 提交容器为镜像 <container_id> 容器id my_migration_image 镜像名称 docker commit <container_id> my_migration_image # 保存镜像为tar文件 docker save my_migration_image > my_migration_image.tar 在另一台电脑上导入上面的镜像&#xff0c;请…...

贪心算法--购买股票

给你一个整数数组 prices &#xff0c;其中 prices[i] 表示某支股票第 i 天的价格。 在每一天&#xff0c;你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买&#xff0c;然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1&a…...

在Mac主机上连接Linux虚拟机

前言 最近醉心于研究Linux&#xff0c;于是在PD上安装了一个Debian Linux虚拟机&#xff0c;用来练练手。但是每次在mac和Linux之间切换很是麻烦&#xff0c;有没有一种方法&#xff0c;可以在mac终端直接连接我的虚拟机&#xff0c;这样在mac终端上就可以直接操控我的Linux虚…...

前端如何单独做虚拟奖金池?

公司业务需求要做一个虚拟奖金池&#xff0c;具体是需求是&#xff0c;不需要后端数据支持&#xff0c;但是又需要不同用户看到的奖金池数据每次变动都是一致的&#xff0c;并且要在给定的最小最大值中变动。 一开始看需求&#xff0c;因为需要所有登录/未登录&#xff0c;不同…...

前端md5校验文件

前端获取文件的md5值&#xff0c;与文件一同传到后端&#xff0c;后端同样对md5值进行校验。如果相同&#xff0c;则文件未被损坏&#xff08;其实这种方式优点类似于tcp、ip的差错校验&#xff0c;好像token也是这种方式&#xff09; 项目准备 前端并不可能手写一个算法来实…...

总结SQL相对常用的几个字符函数

目录 字符的截取 substr() trim()、ltrim()、rtrim() 字符串的拼接 ||、 字符的大小写转换 upper(column_name):大写 lower(column_name):小写 字符替换 replace() 搜索字符 instr(column_name, substring_to_find,start,n_appearence) charindex(substring_to_fi…...

云计算笔记

RAID的组合方式 RAID0&#xff1a;多个硬盘同时工作&#xff0c;可提供性能&#xff0c;无冗余机制 RAID1&#xff1a;数据保存多份&#xff0c;提供冗余机制&#xff0c;性能受到影响 RAID3&#xff1a;存在数据盘和单独校验盘&#xff0c;数据写入 至数据盘后需要运算且将…...

网络安全学习路线-超详细

零基础小白&#xff0c;到就业&#xff01;入门到入土的网安学习路线&#xff01; 在各大平台搜的网安学习路线都太粗略了。。。。看不下去了&#xff01; 建议的学习顺序&#xff1a; 一、网络安全学习普法&#xff08;心里有个数&#xff0c;要进去坐几年&#xff01;&#x…...

【多模态检索】Coarse-to-Fine Visual Representation

快手文本视频多模态检索论文 论文&#xff1a;Towards Efficient and Effective Text-to-Video Retrieval with Coarse-to-Fine Visual Representation Learning 链接&#xff1a;https://arxiv.org/abs/2401.00701 摘要 近些年&#xff0c;基于CLIP的text-to-video检索方法…...

VRRP——虚拟路由冗余协议

什么是VRRP 虚拟路由冗余协议VRRP&#xff08;Virtual Router Redundancy Protocol&#xff09;是一种用于提高网络可靠性的容错协议。 通过VRRP&#xff0c;可以在主机的下一跳设备出现故障时&#xff0c;及时将业务切换到备份设备&#xff0c;从而保障网络通信的连续性和可…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...