【LeetCode热题100】【双指针】盛最多水的容器

给定一个长度为 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 <= n <= 105
  • 0 <= height[i] <= 104

题解 

看到这个题第一个想法是两层循环找最大的乘积

class Solution {
public:int maxArea(vector<int>& height) {auto capacity=[&height](int begin,int end)->int{int h=height[begin]<height[end]?height[begin]:height[end];int width=end-begin;return h*width;};int max=0;for(int i=0;i<height.size()-1;i++){for(int j=i+1;j<height.size();j++){int c=capacity(i,j);max=max<c?c:max;}}return max;}
};

但是超时了

我们把两层循环改成一层循环,使用双指针的方法,让left=0,right=n-1,从两侧的木板开始计算容量

计算完这两块木板的容量之后,我们需要换掉一块木板继续计算容量,换掉哪一块木板呢,我们应该换掉短的那一块木板,因为如果换掉长的那一块木板,那么我们的容量只能缩小,因为容器的高度已经由最短的那块木板决定了,由于我们是从外侧开始换木板的,因此容器的宽度只能缩短不能变长

所以我们每次换掉最短的那一块木板,然后在过程中更新最大容量

class Solution {
public:int maxArea(vector<int>& height) {auto capacity=[&height](int begin,int end)->int{int h=height[begin]<height[end]?height[begin]:height[end];int width=end-begin;return h*width;};int max=0;int left=0,right=height.size()-1;while(left!=right){int c=capacity(left,right);max=max<c?c:max;if(height[left]<height[right]){left++;}else{right--;}}return max;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/209572.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何往excel中写子表?

with pd.ExcelWriter("C:/last_date.xlsx") as writer:for i in range(0, 10):df pd.DataFrame()df.to_excel(writer, indexFalse, sheet_namestr(days[i 1]))

【高效开发工具系列】gson入门使用

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

医院不良事件报告系统源码带鱼骨图分析

医院不良事件上报系统通过 “事前的人员知识培训管理和制度落地促进”、“事中的事件上报和跟进处理”、 以及 “事后的原因分析和工作持续优化”&#xff0c;结合预存上百套已正在使用的模板&#xff0c;帮助医院从对护理事件、药品事件、医疗器械事件、医院感染事件、输血事件…

肺癌二期治疗效果与方案

肺腺癌II期治疗方案主要包括手术治疗、化疗、放疗等&#xff0c;建议患者积极配合医生治疗。 1、手术治疗 肺腺癌属于肺部恶性肿瘤&#xff0c;生长速度比较缓慢&#xff0c;早期患者可以通过手术的方式切除病变部位&#xff0c;能够达到根治目的&#xff0c;术后患者要注意伤…

CTF特训日记day3

复现一下RWCTF5th shellfind题目 题目描述如下&#xff1a; Hello Hacker. You dont know me, but I know you. I want to play a game. Heres what happens if you lose. The device you are watching is hooked into your Saturday and Sunday. When the timer in the back …

没有哈希时间锁定合约的跨链原子交换

在上一篇文章中&#xff0c;我们介绍了使用哈希时间锁定合约&#xff08;HTLC&#xff09;的跨链原子交换实现。 今天&#xff0c;我们介绍一种无需 HTLC 即可实现的替代方法。 这将原子交换扩展到缺乏哈希锁和时间锁的区块链。 使用 SPV 证明交易已被挖掘 让我们按照商定的价…

支撑材料-软件项目质量保证措施-资料大全

一、 质量保障措施 二、 项目质量管理保障措施 &#xff08;一&#xff09; 资深的质量经理与质保组 &#xff08;二&#xff09; 全程参与的质量经理 &#xff08;三&#xff09; 合理的质量控制流程 1&#xff0e; 质量管理规范&#xff1a; 2&#xff0e; 加强协调管理…

【23-24 秋学期】NNDL 作业11 LSTM

习题6-4 推导LSTM网络中参数的梯度&#xff0c; 并分析其避免梯度消失的效果 习题6-3P 编程实现下图LSTM运行过程 李宏毅机器学习笔记&#xff1a;RNN循环神经网络_李宏毅rnn笔记_ZEERO~的博客-CSDN博客https://blog.csdn.net/weixin_43249038/article/details/132650998 L5W…

Spring-AOP与声明式事务

为什么要用AOP ①现有代码缺陷 针对带日志功能的实现类&#xff0c;我们发现有如下缺陷&#xff1a; 对核心业务功能有干扰&#xff0c;导致程序员在开发核心业务功能时分散了精力 附加功能分散在各个业务功能方法中&#xff0c;不利于统一维护 ②解决思路 解决这两个问题&…

Python基础快速过一遍

文章目录 一、变量及基本概念1、变量2、变量类型3、变量格式化输出4、type()函数5、input()函数6、类型转换函数7、注释 二、Python运算/字符1、算数运算2、比较运算3、逻辑运算4、赋值运算符5、转义字符6、成员运算符 三、判断/循环语句1、if判断语句2、while循环语句3、for循…

【ret2user】InCTF2021-Kqueue

前言 这题给了源码&#xff0c;感觉代码的问题很大。然后题目不算难&#xff0c;但是最后 ret2user 执行的代码很有意思。这里的思路是参考的 Roland_ 大佬的思路&#xff1a;[原创]InCTF 内核Pwn之 Kqueue-Pwn-看雪-安全社区|安全招聘|kanxue.com 最后不去泄漏 kernel_offse…

IDEA构建springBoot新项目时JDK只有17和21,无法选择JDK8解决方案

今天创建springboot新项目时&#xff0c;发现IDEA里JDK选项只有17和21&#xff0c;无法选择本机的JDK8&#xff0c;网上查资料后发现是springboot2.7于11.24号后停止维护&#xff0c;基于2.7和java8的spring Initializ官方不再维护&#xff0c;解决方案是在server URL栏&#x…

STM32CubeIde 实现printf打印输出

STM32CubeIde 实现printf打印输出&#xff0c;在IDE生成的程序的main中的/* USER CODE BEGIN 4 /和/ USER CODE END 4 */之间放下面代码&#xff1a; #ifdef __GNUC__ #define PUTCHAR_PROTOTYPE int __io_putchar(int ch) #define GETCHAR_PROTOTYPE int __io_getchar(FILE *…

集线器-交换机-路由器

1.集线器(Hub) 集线器就是将网线集中到一起的机器&#xff0c;也就是多台主机和设备的连接器。集线器的主要功能是对接收到的信号进行同步整形放大&#xff0c;以扩大网络的传输距离&#xff0c;是中继器的一种形式&#xff0c;区别在于集线器能够提供多端口服务&#xff0c;也…

OpenGL 和 OpenGL ES 2.0/3.X 一致性测试说明(CTS)

本文档介绍如何构建、移植和运行 OpenGL 和 OpenGL ES 2.0/3.X 一致性测试&#xff0c;以及如何验证和提交测试结果。 [TOC]目录 测试环境要求 一致性测试需要文件系统。文件系统需要支持长文件名&#xff08;即 > 8.3 名称格式&#xff09;。一致性测试中的源文件使用大…

面试题:MySQL为什么选择B+树作为索引结构

文章目录 前言二、平衡二叉树(AVL)&#xff1a;旋转耗时三、红黑树&#xff1a;树太高四、B树&#xff1a;为磁盘而生五、B树六、感受B树的威力七、总结 前言 在MySQL中&#xff0c;无论是Innodb还是MyIsam&#xff0c;都使用了B树作索引结构(这里不考虑hash等其他索引)。本文…

Redis命令详解

文章目录 Key&#xff08;键&#xff09; DEL EXISTS EXPIRE EXPIREAT PEXPIRE PEXPIREAT PERSIST KEYS TTL PTTL RENAME RENAMENX TYPE SCAN HSCAN SSCAN ZSCAN DUMP String&#xff08;字符串&#xff09; SET GET INCR DECR MSET MGET APPEND SETNX STRLEN INCRBY DECRBY IN…

opencv知识库:cv2.add()函数和“+”号运算符

需求场景 现有一灰度图像&#xff0c;需求是为该图像增加亮度。 原始灰度图像 预期目标图像 解决方案 不建议的方案——“”运算符 假设我们需要为原始灰度图像的亮度整体提升88&#xff0c;那么利用“”运算符的源码如下&#xff1a; import cv2img_path r"D:\pych…

Django二转Day03 04

0 cbv执行流程&#xff0c;self问题 path(index/, Myview.as_view()),Myview.as_view() 实例化后返回 变成return Myview.dispatch(request, *args, **kwargs)但是视图函数Myview中没有 dispatch 方法 所以去 父类View中寻找return View.dispatch(request, *args, **kwargs)调用…

jmeter接口自动化部署jenkins教程

首先&#xff0c;保证本地安装并部署了jenkins&#xff0c;jmeter&#xff0c;xslproc 我搭建的自动化测试框架是jmeterjenkinsxslproc ---注意&#xff1a;原理是&#xff0c;jmeter自生成的报告jtl文件&#xff0c;通过xslproc工具&#xff0c;再结合jmeter自带的模板修改&…