python算法与数据结构---单调栈与实践
单调栈
-
单调栈是一个栈,里面的元素的大小按照它们所在栈的位置,满足一定的单调性;
-
性质:
- 单调递减栈能找到左边第一个比当前元素大的元素;
- 单调递增栈能找到左边第一个比当前元素小的元素;
-
应用场景
- 一般用于解决第一个大于XXX或者第一个小于XXX这一类的题目
-
优点:实践复杂度是线性的,每个元素只遍历一次

-
单调递减栈,每次都能找到左边第一个比它大的数
-
单调递增栈,每次都能找到左边第一个比它小的数

84. 柱状图中最大的矩形
https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

解法一:暴力解法
依次遍历柱形的高度,对于每一个高度分别向两边扩散,求出当前高度为矩形的最大宽度
- 向左遍历,看最多能向左延伸多长,找到大于等于当前柱形高度的最左边元素的下标;
- 向右遍历,看最多能向右延伸多长,找到大于等于当前柱形高度的最右边元素的下标;
- 计算当前高度对应的最大面积,与历史最大值进行比较并更新。
该解法在用例数量过多时,容易超出实时间限制
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:size = len(heights)res = 0for i in range(size):# 找左边最后一个大于等于heights[i]的下标left = icur_height = heights[i]while left > 0 and heights[left-1] >= cur_height:left -= 1# 找右边最后一个大于等于heights[i]的下标right = iwhile right < size-1 and heights[right + 1] >= cur_height:right += 1max_width = right - left + 1res = max(res, max_width * cur_height)return res
解法二:单调栈
- 获取每根柱子左边第一个比它低的柱子坐标,(单调递增栈)
- 获取每根柱子右边第一个比它低的柱子下标,(倒序来做,就是左边第一个比它低的柱子)
- 遍历每根柱子求最大面积
- 哨兵技巧:两边各添加一个虚拟柱子
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:stack = []left = [0 for _ in range(len(heights))]right = [0 for _ in range(len(heights))]res = 0# 获取每根柱子左边第一个比它低的柱子下标for i in range(len(heights)):while stack and heights[stack[-1]] >= heights[i]:stack.pop()if not stack:left[i] = -1else:left[i] = stack[-1]stack.append(i)stack = []# 获取每根柱子右边第一个比它低的柱子下标for j in range(len(heights) - 1, -1, -1):while stack and heights[stack[-1]] >= heights[j]:stack.pop()if not stack:right[j] = len(heights)else:right[j] = stack[-1]stack.append(j)# 求最大面积for i in range(len(heights)):res = max(res, heights[i] * (right[i] - left[i] - 1))return res
- 单调栈图示:(获取每根柱子右边第一个比它低的柱子下标,则需要倒序来做)

附录基础
python数据结构与算法理论基础(专栏)
数据结构与算法(python)http://t.csdnimg.cn/Gb6MN
程序 = 数据结构 + 算法;而且在面试过程中这些是必考,必问的内容。内容大纲:基础数据结构(树、链表、栈、队列等)、常见算法(排序算法、递归算法等)。
专栏是基于python的基础知识,是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念,同时结合力扣题目,也能更好的掌握这些知识,达到在面试中游刃有余的效果。
python基础语法
python基础精讲 http://t.csdnimg.cn/HdKdi
本专栏主要针对python基础语法,帮助学习者快速接触并掌握python大部分最重要的语法特征。
1、基本数据类型和变量
2、分支结构与循环结构
3、函数与异常处理
4、类与模块
5、文件读写
通过本专栏可以快速掌握python的基础语法。
相关文章:
python算法与数据结构---单调栈与实践
单调栈 单调栈是一个栈,里面的元素的大小按照它们所在栈的位置,满足一定的单调性; 性质: 单调递减栈能找到左边第一个比当前元素大的元素;单调递增栈能找到左边第一个比当前元素小的元素; 应用场景 一般用…...
文心一言使用分享
ChatGPT 和文心一言哪个更好用? 一个直接可以用,一个还需要借助一些工具,还有可能账号会消失…… 没有可比性。 通用大模型用于特定功能的时候需要一些引导技巧。 import math import time def calculate_coordinate(c, d, e, f, g, h,…...
【C++干货铺】C++11新特性——lambda表达式 | 包装器
个人主页点击直达:小白不是程序媛 C系列专栏:C干货铺 代码仓库:Gitee 目录 C98中的排序 lambda表达式 lambda表达式语法 表达式中的各部分说明 lambda表达式的使用 基本的使用 [var]值传递捕捉变量var 编辑 [&var]引用传递捕…...
在 EggJS 中实现 Redis 上锁
配置环境 下载 Redis Windows 访问 https://github.com/microsoftarchive/redis/releases 选择版本进行下载 - 勾选 [配置到环境变量] - 无脑下一步并安装 命令行执行:redis-cli -v 查看已安装的 Redis 版本,能成功查看就表示安装成功啦~ Mac brew i…...
Unity-场景
创建场景 创建新的场景后: 文件 -> 生成设置 -> Build中的场景 -> 将项目中需要使用的场景拖进去 SceneTest public class SceneTest : MonoBehaviour {// Start is called before the first frame updatevoid Start(){// 两个类: 场景类、场…...
MATLAB R2023b for Mac 中文
MATLAB R2023b 是 MathWorks 发布的最新版本的 MATLAB,适用于进行算法开发、数据可视化、数据分析以及数值计算等任务的工程师和科学家。它包含了一系列新增功能和改进,如改进了数据导入工具,增加了对数据帧和表格对象的支持,增强…...
01 MyBatisPlus快速入门
1. MyBatis-Plus快速入门 版本 3.5.31并非另起炉灶 , 而是MyBatis的增强 , 使用之前依然要导入MyBatis的依赖 , 且之前MyBatis的所有功能依然可以使用.局限性是仅限于单表操作, 对于多表仍需要手写 项目结构: 先导入依赖,比之前多了一个mybatis-plus…...
HarmonyOS 应用开发入门
HarmonyOS 应用开发入门 前言 DevEco Studio Release版本为:DevEco Studio 3.1.1。 Compile SDK Release版本为:3.1.0(API 9)。 构建方式为 HVigor,而非 Gradle。 最新版本已不再支持 (”Java、JavaScrip…...
【机器学习300问】9、梯度下降是用来干嘛的?
当你和我一样对自己问出这个问题后,分析一下!其实我首先得知道梯度下降是什么,也就它的定义。其次我得了解它具体用在什么地方,也就是使用场景。最后才是这个问题,梯度下降有什么用?怎么用? 所以…...
第13章 1 进程和线程
文章目录 程序和进程的概念 p173函数式创建子进程Process类常用的属性和方法1 p175Process类中常用的属性和方法2 p176继承式创建子进程 p177进程池的使用 p178并发和并行 p179进程之间数据是否共享 p180队列的基本使用 p180使用队列实现进程之间的通信 p182函数式创建线程 p18…...
什么是中间件?
文章目录 为什么需要中间件?中间件生态漫谈数据库中间件读写分离分库分表引进数据库中间件MyCat 服务端代理模式ShardingJDBC 客户端代理模式 总结 IT 系统从单体应用逐渐向分布式架构演变,高并发、高可用、高性能、分布式等话题变得异常火热,…...
汽车售后服务客户满意度调查报告
本文由群狼调研(长沙旅行社满意度调查)出品,欢迎转载,请注明出处。汽车售后服务客户满意度调查报告通常包括以下内容: 1.调研概况:介绍调研的目的、背景和范围,包括调研的时间、地点和样本规模等…...
初始RabbitMQ(入门篇)
消息队列(MQ) 本质上就是一个队列,一个先进先出的队列,队列中存放的内容是message(消息),是一种跨进程的通信机制,用于上下游传递消息, 为什么使用MQ: 削峰填谷: MQ可以很好的做一个缓冲机制,例如在一个系统中有A和B两个应用,A是接收用户的请求的,然后A调用B进行处理. 这时…...
JVM:Java类加载机制
Java类加载机制的全过程: 加载、验证、准备、初始化和卸载这五个阶段的顺序是确定的,类型的加载过程必须按照这种顺序按部就班地开始,而解析阶段则不一定:它在某些情况下可以在初始化阶段之后再开始, 这是为了支持Java…...
要经历痛苦,才能在赚钱路上觉醒!
新手赚钱,一个秘诀就够了! 黎明前的黑暗实际是最漫长的,就如同开发进度99%到100%这个过程尤其漫长。赚钱的路上起初就是黑暗,不断地摸索最终才能走出迷雾,真正的迎接朝阳。如果有一段路程,十来公里的路线&a…...
LeetCode 第381场周赛个人题解
目录 100191. 输入单词需要的最少按键次数 I 原题链接 题目描述 思路分析 AC代码 100188. 按距离统计房屋对数目 I 原题链接 题目描述 思路分析 AC代码 100192. 输入单词需要的最少按键次数 II 原题链接 题目描述 思路分析 AC代码 100213. 按距离统计房屋对数目…...
数据结构之二叉树的性质与存储结构
数据结构之二叉树的性质与存储结构 1、二叉树的性质2、二叉树的存储结构 数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,…...
机器视觉检测设备在连接器外观缺陷检测中的应用
作为传输电流或信号连接两个有源器件的器件,连接器被广泛应用于各个行业,从手机、平板、电脑,到冰箱、空调、洗衣机,再到汽车、国防、航空,处处是它的所在。每个电子产品少了连接器将无法运作,因此…...
ChatGPT vs 文心一言(AI助手全面比较)
随着人工智能的不断发展,ChatGPT(OpenAI)和文心一言都代表了当前先进的自然语言处理技术。它们在智能回复、语言准确性和知识库丰富度等方面都有各自的优势。在下面的比较中,我们将从多个角度探讨这两个AI助手,帮助你更…...
MSPM0L1306例程学习-UART部分(2)
MSPM0L1306例程学习系列 1.背景介绍 写在前边的话: 这个系列比较简单,主要是围绕TI官网给出的SDK例程进行讲解和注释。并没有针对模块的具体使用方法进行描述。所有的例程均来自MSPM0 SDK的安装包,具体可到官网下载并安装: https://www.ti…...
HunyuanVideo-Foley实战案例:为纪录片自动匹配环境音效的完整工作流
HunyuanVideo-Foley实战案例:为纪录片自动匹配环境音效的完整工作流 1. 项目背景与需求 在纪录片制作过程中,环境音效的采集和匹配往往需要耗费大量时间和人力成本。传统方式需要音效师实地录制或从音效库中手动挑选,整个过程耗时且难以保证…...
【单片机】内核中断及NVICPending
红色框住的是M3内核中断,青色框住的默认打开,不可关闭中断(除NMI外可屏蔽)。包括SysTick在内无需NVIC_EnableIRQ,也无需在中断处理函数里清标志位。NVIC_SetPendingIRQ和NVIC_ClearPendingIRQ基本用不到,任…...
从零上手Neo4j Desktop:CSV数据导入与核心Cypher操作指南
1. Neo4j Desktop环境准备与数据导入 第一次打开Neo4j Desktop时可能会被它的界面搞得有点懵,别担心,我刚开始用的时候也这样。这个工具把数据库管理、浏览器界面和插件都集成在了一起,特别适合新手快速上手。安装过程我就不赘述了࿰…...
大模型RAG入门基础架构介绍
传统大模型的局限性 知识可能过时(训练数据有时效 性)会产生"幻觉"(编造不存在的信息)无法访问私有知识库数据回答缺乏具体出处,难以验证最大对话上下文限制(大部分模型128K) RAG的…...
OpenArk:新一代Windows系统安全分析工具完整指南
OpenArk:新一代Windows系统安全分析工具完整指南 【免费下载链接】OpenArk The Next Generation of Anti-Rookit(ARK) tool for Windows. 项目地址: https://gitcode.com/GitHub_Trending/op/OpenArk 如果你正在寻找一款强大的Windows系统安全分析工具&#…...
PyTorch张量拼接实战:torch.stack()与torch.cat()的5个典型场景对比
PyTorch张量拼接实战:torch.stack()与torch.cat()的5个典型场景对比 在深度学习项目中,数据维度的操作就像乐高积木的拼装——选错连接方式可能导致模型结构崩塌。作为PyTorch中高频使用的两种拼接操作,torch.stack()和torch.cat()常被混淆使…...
如何高效提取网页SVG内容:3步实现可视化数据导出
如何高效提取网页SVG内容:3步实现可视化数据导出 【免费下载链接】svg-crowbar Extracts an SVG node and accompanying styles from an HTML document and allows you to download it all as an SVG file. 项目地址: https://gitcode.com/gh_mirrors/sv/svg-crow…...
Dify工作流终极指南:3天从新手到专家的完整免费教程
Dify工作流终极指南:3天从新手到专家的完整免费教程 【免费下载链接】Awesome-Dify-Workflow 分享一些好用的 Dify DSL 工作流程,自用、学习两相宜。 Sharing some Dify workflows. 项目地址: https://gitcode.com/GitHub_Trending/aw/Awesome-Dify-Wo…...
Wireshark抓包实战:DHCP协议交互全流程解析(附常见问题排查)
Wireshark深度解析:DHCP协议交互全流程与实战排错指南 从零开始理解DHCP协议的本质 想象一下,当你带着笔记本电脑走进一家咖啡馆,连接Wi-Fi的瞬间,设备就自动获得了上网所需的所有配置——IP地址、子网掩码、默认网关、DNS服务器。…...
Word空白页删不掉?【图文讲解】怎么删除word空白页?word批量删除空白页?5种方法教你彻底删除
(1)问题背景谁在编辑 Word 时没被顽固空白页气到抓狂?写论文、做报告、整理文案,明明内容已经结束,页面末尾偏偏多出一页空白,删也删不掉、退也退不去。打印时白白浪费纸张,上交文档显得格外不专…...
