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

leetcode分类刷题:基于数组的双指针(四、小的移动)

leetcode上有些题是真的太难了,正常读题之后完全想不到要用双指针来求解,本次博客总结的题目是双指针初始时位于数组两端,哪个元素小就移动哪个指针

11. 盛最多水的容器

1、这道题放在42. 接雨水的相似题目里,可能是因为它们都有相似的双指针解法吗?从解题代码上看,可能本题的双指针更好理解一些
2、解题思路:左右指针从两侧同时遍历,哪个指针对应的元素小就更新哪个指针,等价于对应的面积可能变大;这个思路巧妙但不是那么好想

from typing import List
'''
11. 盛最多水的容器
给定一个长度为 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。
题眼:
思路:双指针:左右指针从两侧同时遍历,哪个指针对应的元素小就更新哪个指针,等价于对应的面积可能变大;这个思路巧妙但不是那么好想
'''class Solution:def maxArea(self, height: List[int]) -> int:left, right = 0, len(height) - 1result = min(height[left], height[right]) * (right - left)  # result初始值为处于数组边界情况的面积while left < right:if height[left] >= height[right]:  # 更新right才可能获得更大面积right -= 1elif height[left] < height[right]:  # 更新left才可能获得更大面积left += 1result = max(result, min(height[left], height[right]) * (right - left))return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')height = [int(n) for n in in_line[1].strip()[1: -1].split(',')]print(obj.maxArea(height))except EOFError:break

42. 接雨水

1、下一个更大的数的变体题目,即左右两边下一个最大的数:这道题目最关键的地方在于理解题目,每个位置接雨水的量取决于左右两边的最大值,因此按照该思路定义两个数组,分别保存左右两边的最大值,然后再次遍历序列依次累计雨水量即可
2、这道题也可以按照单调栈的解法思路:按照“大小大”规律求夹着的面积,与栈的先入后出思想一致:小于栈顶元素入栈;等于栈顶元素则替换栈顶元素;大于栈顶元素则判断“大小大”计算面积,按照行为单位求雨水量
3、这道题还可以用双指针的解法思路:左右指针从两侧同时遍历,并分别维护左右两侧的最大值标记,哪个指针对应的元素小就更新哪个,等价于哪个指针可以根据两个最大值标记计算接水量,就移动哪个指针;这个思路巧妙但更难了,不是太常规

from typing import List
'''
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水
示例 1:输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
题眼:
思路1、模拟:每个位置接雨水的量取决于左右两边的最大值,因此,定义两个数组,分别保存左右两边的最大值(包括自己,闭区间考虑);这种思路是按照列为单位求
雨水量的,简单直观,建议掌握!
思路2、单调栈:按照“大小大”规律求夹着的面积,与栈的先入后出思想一致:小于栈顶元素入栈;等于栈顶元素则替换栈顶元素;大于栈顶元素则判断“大小大”计算面积;
这种思路按照行为单位求雨水量的,这种解释不是太好理解,还不如按照括号配对的思路理解,按照这种思路有点难
思路3、双指针:左右指针从两侧同时遍历,并分别维护左右两侧的最大值标记,哪个指针对应的元素小就更新哪个,等价于哪个指针可以根据两个最大值标记计算接水量,
就移动哪个指针;这个思路巧妙但更难了,不是太常规,理解起来有点吃力
'''class Solution:def trap(self, height: List[int]) -> int:# # 思路1、模拟:每个位置接雨水的量取决于左右两边的最大值,因此,定义两个数组,分别保存左右两边的最大值(包括自己,闭区间考虑)# lmax = [0] * len(height)# maxNum = 0# for i in range(len(height)):#     maxNum = max(maxNum, height[i])#     lmax[i] = maxNum# rmax = [0] * len(height)# maxNum = 0# for i in range(len(height) - 1, -1, -1):#     maxNum = max(maxNum, height[i])#     rmax[i] = maxNum# result = 0# for i in range(len(height)):#     result += min(lmax[i], rmax[i]) - height[i]# return result# # 思路2、单调栈:按照“大小大”规律求夹着的面积,与栈的先入后出思想一致:小于栈顶元素入栈;等于栈顶元素则替换栈顶元素;# # 大于栈顶元素则判断“大小大”计算面积# stk = []# result = 0# for i in range(len(height)):#     if len(stk) == 0:#         stk.append(i)#     else:#         if height[i] < height[stk[-1]]:#             stk.append(i)#         elif height[i] == height[stk[-1]]:  # 这一步可以注释掉,合并到上一步入栈#             stk.pop()#             stk.append(i)#         elif height[i] > height[stk[-1]]:#             while len(stk) > 0 and height[i] > height[stk[-1]]:#                 right = height[i]#                 mid = height[stk.pop()]#                 if len(stk) > 0:#                     left = height[stk[-1]]#                     result += (min(left, right) - mid) * (i - stk[-1] - 1)#             stk.append(i)# return result# 思路3、双指针:左右指针从两侧同时遍历,并分别维护左右两侧的最大值标记,哪个指针对应的元素小就更新哪个,等价于哪个指针可以根据两个最大值标# 记计算接水量,就移动哪个指针left, right = 0, len(height) - 1lMax, rMax = height[left], height[right]  # lMax标记了left位置的左侧最大值(包括left本身);rMax标记了right位置的右侧最大值# (包括right本身)result = 0while left < right:  # left==right时,表示定位到了数组中的最大值处了,这里不用计算,肯定不能接水if height[left] <= height[right]:  # 情况1:height[left]刚好为lMax,必有lMax<=rMax;情况2:height[left]之前的某个数# 为lMax,那么当时left能更新的条件必然是lMax<=rMax;那么在left位置,必然有lMax<=left位置自己的右侧最大值(本来就比rMax大)# 所以,left指针可以记计算接水量result += lMax - height[left]  # 因为lMax包含了left位置,所以不用担心该计算小于0left += 1lMax = max(lMax, height[left])elif height[left] > height[right]:  # 情况1:height[right]刚好为rMax,必有lMax>rMax;情况2:height[right]之前的某个数# 为lMax,那么当时right能更新的条件必然是lMax>rMax;那么在right位置,必然有right位置自己的左侧最大值(本来就比lMax大)>rMax# 所以,right指针可以记计算接水量result += rMax - height[right]  # 因为rMax包含了right位置,所以不用担心该计算小于0right -= 1rMax = max(rMax, height[right])return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')height = [int(n) for n in in_line[1].strip()[1: -1].split(',')]print(obj.trap(height))except EOFError:break

相关文章:

leetcode分类刷题:基于数组的双指针(四、小的移动)

leetcode上有些题是真的太难了&#xff0c;正常读题之后完全想不到要用双指针来求解&#xff0c;本次博客总结的题目是双指针初始时位于数组两端&#xff0c;哪个元素小就移动哪个指针 11. 盛最多水的容器 1、这道题放在42. 接雨水的相似题目里&#xff0c;可能是因为它们都有相…...

eclipse

快捷键 F4: 继承树 F3: 查看变量、方法、类的定义, 跳到光标所在标识符的定义代码。(Ctrl左键) CtrlShiftG&#xff1a; 在工作空间中查找引用了光标所在标识符的位置。与F3相反的快捷键。当按类定义进行阅读时&#xff0c;当前类方法或者函数在被哪些地方调用 controlTAB: 切…...

VIT中的einops包详解

‘’‘einops有三个常用方法&#xff1a;rearrange,repeat,reduce’‘’ rearrange的操作相当于转置 rearrange(image,‘h w c -> w h c’) 高和宽转置 path ../data/cat_and_mouse.jpg image cv2.imread(path) h,w,c image.shape # shape第一个值是h,第二个是w image…...

目标检测笔记(十三): 使用YOLOv5-7.0版本对图像进行目标检测完整版(从自定义数据集到测试验证的完整流程))

文章目录 一、目标检测介绍二、YOLOv5介绍2.1 和以往版本的区别 三、代码获取3.1 视频代码介绍 四、环境搭建五、数据集准备5.1 数据集转换5.2 数据集验证 六、模型训练七、模型验证八、模型测试九、评价指标 一、目标检测介绍 目标检测&#xff08;Object Detection&#xff…...

【数据结构】设计环形队列

环形队列是一种线性数据结构&#xff0c;其操作表现基于 FIFO&#xff08;先进先出&#xff09;原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 环形队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里&#xff0c;一旦一个队列…...

无涯教程-JavaScript - COUPDAYSNC函数

描述 COUPDAYSNC函数返回从结算日期到下一个息票日期的天数。 语法 COUPDAYSNC (settlement, maturity, frequency, [basis])争论 Argument描述Required/OptionalSettlement 证券的结算日期。 证券结算日期是指在发行日期之后将证券交易给买方的日期。 RequiredMaturity 证…...

python 随机生成emoji表情

问答板块觉得比较有意思的问题 当时搜了些网上的发现基本都不能用&#xff0c;不知道是版本的问题还是咋的就开始自己研究 python随机生成emoji 问题的产生解决官网文档数据类型实现思路实现前提&#xff1a;具体实现&#xff1a; 其他常见用法插入 Emoji 表情&#xff1a;解析…...

python关闭指定进程以excel为例

先说下环境&#xff1a; Excel版本&#xff1a; Python2.7.13和Python3.10.4并存。 2、打开两个excel工作簿 看进程是这样的&#xff1a; 3、用python编程kill进程 # -*- coding: utf-8 -*- import os proc_nameEXCEL.EXE if __name__ __main__:os.system(taskkill /im {} /…...

前后端中的异步和事件机制 | 前后端开发

前言 在前后端程序设计开发工作中&#xff0c;小伙伴们一定都接触过事件、异步这些概念。出现这些概念的原因之一是&#xff0c;我们的代码在执行过程中所涉及的逻辑在不同的场合下执行时间的期望是各不相同的。为了尽量做到充分利用CPU等资源做尽可能多的事&#xff0c;免不了…...

设计模式篇(Java):装饰者模式

&#x1f468;‍&#x1f4bb;本文专栏&#xff1a;设计模式篇-装饰者模式 &#x1f468;‍&#x1f4bb;本文简述&#xff1a;装饰者模式的详解以及jdk中的应用 &#x1f468;‍&#x1f4bb;上一篇文章&#xff1a; 设计模式篇(Java)&#xff1a;桥接模式 &#x1f468;‍&am…...

Spark【RDD编程(三)键值对RDD】

简介 键值对 RDD 就是每个RDD的元素都是 &#xff08;key&#xff0c;value&#xff09;类型的键值对&#xff0c;是一种常见的 RDD&#xff0c;可以应用于很多场景。 因为毕竟通过我们之前Hadoop的学习中&#xff0c;我们就可以看到对数据的处理&#xff0c;基本都是以…...

从板凳围观到玩转行家:Moonbeam投票委托如何让普通用户一同参与

今年5月&#xff0c;Moonbeam发起了一项社区链上治理中投票委托反馈的调查。187位社区成员参与了这项调查&#xff0c;调查发现受访者对治理感兴趣&#xff0c;增加参与度只需要进行一些调整&#xff0c;即更简化的投票流程。 治理和去中心化是Web3的核心&#xff0c;随着Moon…...

SpringMVC的文件上传文件下载多文件上传---详细介绍

目录 前言&#xff1a; 一&#xff0c;文件上传 1.1 添加依赖 1.2 配置文件上传解析器 1.3 表单设置 1.4 文件上传的实现 二&#xff0c;文件下载 controller层 前端jsp 三&#xff0c;多文件上传 Controller层 运行 前言&#xff1a; Spring MVC 是一个基于 Java …...

Spark【RDD编程(四)综合案例】

案例1-TOP N个数据的值 输入数据&#xff1a; 1,1768,50,155 2,1218,600,211 3,2239,788,242 4,3101,28,599 5,4899,290,129 6,3110,54,1201 7,4436,259,877 8,2369,7890,27 处理代码&#xff1a; def main(args: Array[String]): Unit {//创建SparkContext对象val conf…...

Golang报错mixture of field:value and value initializers

Golang报错mixture of field:value and value initializers 这个错误跟编程习惯&#xff08;模式&#xff09;有关&#xff0c;都知道golang 语言的编程与java /python 以及其他的编程语言相似 &#xff0c;一通百通&#xff0c;易学万卷书。 编程中同一个结构中要保持唯一模…...

【网络教程】记一次使用Docker手动搭建BT宝塔面板的全过程(包含问题解决如:宝塔面板无法开启防火墙,ssh,nginx等)

文章目录 准备安装安装宝塔面板开启ssh和修改ssh的密码导出镜像问题解决宝塔面板无法开启防火墙无法启动ssh设置密码nginx安装失败设置开机启动相关服务准备 演示的系统环境:Ubuntu 22.04.3 LTS更新安装/升级docker到最新版本升级docker相关命令如下# 更新软件包列表并自动升级…...

【大虾送书第九期】速学Linux:系统应用从入门到精通

目录 &#x1f36d;写在前面 &#x1f36d;为什么学习Linux系统 &#x1f36d;Linux系统的应用领域 &#x1f36c;&#xff11;.Linux在服务器的应用 &#x1f36c;&#xff12;.嵌入式Linux的应用 &#x1f36c;&#xff13;.桌面Linux的应用 &#x1f36d;Linux的版本选择 &a…...

docker相关命令

####### 帮助启动类命令 ########## 启动docker systemctl start docker 停止docker systemctl stop docker 重启docker systemctl restart docker 查看docker状态 systemctl status docker 开机启动 systemctl enable docker 查看docker概要信息 docker info 查看…...

【Redis】4、rsync远程同步

与inodify结合使用&#xff0c;实现实时同步 rsync简介 rsync&#xff08;Remote Sync&#xff0c;远程同步&#xff09;是一个开源的快速备份工具&#xff0c;可以在不同主机之间镜像同步整个目录树&#xff0c;&#xff1b;支持增量备份&#xff0c;并保持链接和权限&#…...

无服务架构--Serverless

无服务架构 无服务架构&#xff08;Serverless Architecture&#xff09;即无服务器架构&#xff0c;也被称为函数即服务&#xff08;Function as a Service&#xff0c;FaaS&#xff09;&#xff0c;是一种云计算模型&#xff0c;用于构建和部署应用程序&#xff0c;无需关心…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...