LeetCode十一题:容纳最多水的容器【11/1000 python】

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python
作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

“容纳最多水的容器”是一个经典的数组和双指针问题,考验的是对空间利用和指针操作的理解。本文将通过不同的算法解决这个问题,并提供代码示例及详细的解题步骤。

问题描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

注意:你不能倾斜容器。

输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:数组中的第二个和最后一个元素形成的容器可以容纳最多的水,其面积为 49。

解题思路

方法一:暴力法

最直观的方法是尝试所有可能的两点组合,计算它们能形成的容器的面积,然后找出最大值。

解题步骤
  1. 遍历每一对索引组合 (i, j),其中 0 <= i < j < n
  2. 对每对索引计算容器的面积:Area = min(height[i], height[j]) * (j - i)
  3. 记录并更新最大面积。
python示例
def maxArea_v1(height: [int]) -> int:
    max_area = 0
    for i in range(len(height)):
        for j in range(i + 1, len(height)):
            area = min(height[i], height[j]) * (j - i)
            max_area = max(max_area, area)
    return max_area

复杂度分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

方法二:双指针法

双指针法是解决这个问题的最佳方法,它利用了“向内移动短板可以找到可能的更大面积”的直觉。

解题步骤
  1. 初始化两个指针分别指向数组的开头和结尾。
  2. 计算当前两个指针形成的容器的面积,并更新最大面积。
  3. 移动较短的一边的指针向内,直到两个指针相遇。
python示例
def maxArea(height: [int]) -> int:
    max_area, left, right = 0, 0, len(height) - 1
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
双指针图解
初始状态

设想一个容器的左右边界由线段的两端组成。此时,左指针在数组的最开始位置(索引 0),右指针在数组的最末尾位置(索引 len(height) - 1)。这个容器的宽度是最大的。

  [1,8,6,2,5,4,8,3,7]
   ^               ^
   |               |
 left           right
移动指针

接下来,我们比较左右指针指向的高度。为了增加容器的高度,我们总是向内移动较矮的边,因为容器的实际高度由较矮的那边决定。在每一步中,我们计算当前指针指向的容器能容纳的水量,并更新最大值。

如果左边较矮:
[1,8,6,2,5,4,8,3,7]
   ^             ^
  left         right
如果右边较矮:

如果在某一步中,右指针指向的高度小于左指针指向的高度,那么我们移动右指针向左一位。

[1,8,6,2,5,4,8,3,7]
   ^           ^
  left       right
结束条件

当左右指针相遇时,我们已经考虑了所有可能的容器,循环结束。

总结

“容纳最多水的容器”问题通过暴力法可以直观地理解问题,但双指针法在效率上大大提升,是解决这类问题的典型示例。学会双指针技巧不仅可以帮助我们优雅地解决这个问题,也是提升算法解题能力的重要手段。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

信息系统项目管理师——第18章项目绩效域管理(一)

本章节内容属于第四版新增知识&#xff0c;为PMBOK第七版专有&#xff0c;选择、案例、论文都会考&#xff0c;属于比较重要的章节。 选择题&#xff0c;稳定考3分左右&#xff0c;新教材基本考课本原话&#xff0c;需要多读课本&#xff0c;多刷题。 案例题&#xff0c;考的概…

SpringBoot快速入门笔记(3)

文章目录 一、MybatisPlus1、ORM2、添加依赖3、全局配置4、Navicat5、UserController6、CRUD操作7、BaseMapper8、两个注解 二、多表查询1、模拟用户订单2、通过用户查相关订单3、UserMapperNew4、查询订单和所属用户5、OrderMapper6、OrderController 三、条件查询四、分页查询…

C++之类

目录 一&#xff1a;面向过程和面向对象的初步认识 二&#xff1a;类的引入 三&#xff1a;类的定义 3.1类的两种定义方式&#xff1a; 3.2成员变量命名的建议 四&#xff1a;类的访问限定符及封装 4.1类的访问限定符 4.2封装 一&#xff1a;面向过程和面向对象的初步认…

【学习笔记】java项目—苍穹外卖day09

文章目录 用户端历史订单模块1. 查询历史订单1.1 需求分析和设计1.2 代码实现1.2.1 user/OrderController1.2.2 OrderService1.2.3 OrderServiceImpl1.2.4 OrderMapper1.2.5 OrderMapper.xml1.2.6 OrderDetailMapper 1.3 功能测试 2. 查询订单详情2.1 需求分析和设计2.2 代码实…

【计算机考研】408到底有多难?值得冲吗?

考408就必须要面对的现实&#xff01;拒绝眼高手低&#xff01;&#xff01; 408其实想达到110并不难&#xff0c;但是想上130是比较困难的。 几个必须要面对的现实&#xff1a; 1.如果备考的是11408&#xff0c;除非基础特别好或者学习能力特别强&#xff0c;否则一定要尽早…

[Python] 如何导出PDF文件中的图片

文章目录 一、背景说明二、代码编写三、问题3.1、如何得到图片的xref&#xff1f;3.2、xref有什么用呢&#xff1f; 四、总结 一、背景说明 最近在看一份pdf的书籍&#xff0c;其中有一些图片绘制地比较出色&#xff0c;所以就打算将其复制出来&#xff0c;以便于在需要的时候…

TCP客户端及服务器端开发实践

一、TCP客户端及服务器端开发实践 1、TCP网络应用程序开发分类 ① TCP客户端应用程序开发 ② TCP服务器端应用程序开发 客户端程序是指运行在用户设备上的程序&#xff0c;服务端程序是指运行在服务器设备上的程序&#xff0c;专门为客户端提供数据服务。那如何记忆呢&…

深入浅出 -- 系统架构之单体架构

单体架构&#xff08;Monolithic Architecture&#xff09; 单体架构的定义 单体架构&#xff08;Monolithic Architecture&#xff09;是一种传统的软件架构模式&#xff0c;将整个应用程序作为一个单一的、统一的单元进行开发、部署和扩展。在单体架构中&#xff0c;所有的功…

【数字图像处理matlab系列】空间域处理之亮度变换(imadjust函数使用)

【数字图像处理matlab系列】空间域处理之亮度变换(imadjust函数使用) 在空间域中&#xff0c;图像处理就是直接对图像的像素进行操作 imadjust 是 MATLAB 中用于调整图像强度值或颜色图的函数。它可以改变图像的对比度&#xff0c;使得图像更清晰或更易于分析。以下是 imadju…

计算机网络针对交换机的配置

实验 目的 交换机的基本配置&#xff0c;交换机VLAN配置 实验条件 Windows&#xff0c;Cisco packet tracer 实验 内容 交换机的基本配置&#xff0c;交换机VLAN配置 实验 过程 一、交换机的基本配置 进入特权模式 Switch>enable 进入配置模式 Switch#configure ter…

第15届蓝桥杯省赛模拟第二期题解及代码实现

试题A:求余数 问题描述 求12345678901234567890123456789012345678901234567890除以2023的余数。 答案提交 这是一道结果填空的题&#xff0c;你只需要算出结果后提交即可。本题的结果为一个整数&#xff0c;在提交答案时只填写这个整数&#xff0c;填写多余…

kubectl explain资源文档命令

学习并使用了一段时间的kubernetes&#xff0c;发现对k8s还是了解甚少&#xff0c;于是利用上下班通勤的时间又去B站看一些大佬的视频&#xff0c;又来重学巩固一遍知识&#xff0c;并做些记录。 之前在学习使用过程中未成了解过explain这个命令&#xff0c;因为自己部署的版本…

三、keepalived双机热备

一、双机热备概述 1、为什么需要双机热备&#xff1a; 双机热备主要为了解决服务器的单点故障问题。 在主机 MASTER 宕机之后可以马上切换到备选服务器 BACKUP。 服务器规划&#xff1a; 2、克隆产生web01服务器&#xff1a; (1) 基于LNMP克隆生成Web01服务器&#xff1a; (…

【TB作品】MSP430单片机读取大气压强传感器BMP180

文章目录 实物main所有代码 实物 main #include <msp430.h> #include "stdio.h" #include "OLED.h"#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>// P2.2 oled scl // P2.3 oled sda// p…

第六期丨酷雷曼无人机技能培训

第6期无人机技能提升培训 盼望着盼望着&#xff0c;第六期无人机技能提升培训会终于如期和大家见面了。 2024年1月1日&#xff0c;国务院、中央军事委员会颁布《无人驾驶航空器飞行管理暂行条例》&#xff0c;对民用无人机飞行活动实施更为严格的规范约束&#xff0c;越来越多…

第十四篇:web后端开发-Springboot

文章目录 一、Web入门1. 什么是Spring2. SpringBootWeb入门3. HTTP 协议3.1 HTTP-概述3.2 HTTP-请求协议3.3 HTTP-响应协议 4. Web服务器4.1 Tomcat---简介4.2 基本使用 5. 请求/响应5.1 请求5.1.1 postman5.1.2 简单参数5.1.3 实体参数5.1.4 数组集合参数5.1.5 日期参数5.1.6 …

echart 仪表盘实现指针的渐变色及添加图片

需求&#xff1a; 在仪表盘中设置指针为渐变色&#xff0c;并在仪表盘中间添加图片。 实现重点&#xff1a; 1、仪表盘指针渐变色的实现 渐变色通过设置pointer的itemStyle属性内的color实现&#xff0c;重点是echart版本&#xff0c;这个原本使用4.8.0的版本不起作用&#xff…

33---PS2-键盘鼠标电路设计

视频链接 PS2-键盘鼠标电路设计01_哔哩哔哩_bilibili PS2-键盘鼠标电路设计 1、PS/2简介 PS/2原是“personal 2”的意思&#xff0c;即“个人系统2”&#xff0c;是IBM公司在上个世纪80年代推出的一种个人电脑。 PS/2协议和接口最初由IBM公司开发并广泛使用的应用于键盘/鼠…

速通数据结构与算法第四站 双链表

系列文章目录 速通数据结构与算法系列 1 速通数据结构与算法第一站 复杂度 http://t.csdnimg.cn/sxEGF 2 速通数据结构与算法第二站 顺序表 http://t.csdnimg.cn/WVyDb 3 速通数据结构与算法第三站 单链表 http://t.csdnimg.cn/cDpcC 感谢佬们…

有人用GPT来做日内交易,居然赚钱了!但是……

在我们还在烦恼会不会被AI替代时&#xff0c;已经有人在教ChatGPT去炒股票了。 在近年ChatGPT火速出圈后&#xff0c;围绕AI能取代什么职业的讨论持续受到大众关注。 从事客服、编程、法律合规以及内容创作等行业人员最早感受到这股AI带来的寒意。 那ChatGPT能不能替代交易员…