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…...
PP实战指南:ECN工程变更在物料计划中的关键应用与系统操作解析
1. ECN工程变更的核心价值与业务场景 第一次接触ECN(Engineering Change Notice)是在2015年负责汽车零部件项目时,当时产线因为一个螺丝规格变更导致全线停产8小时。这个惨痛教训让我深刻理解到,工程变更绝不是简单的技术文档更新…...
用MediaPipe和Python做个隔空切水果游戏:从手势骨架提取到简单游戏逻辑实现
用MediaPipe和Python打造体感切水果游戏:从手势识别到游戏逻辑全解析 还记得小时候在街机厅玩《水果忍者》的畅快感吗?现在,我们完全可以用Python和MediaPipe技术,在电脑前通过手势隔空切水果!本文将带你从零开始&…...
手把手教你用XCVU3P和FMC+接口搭建高性能PCIe载板(附原理图下载)
基于XCVU3P与FMC的高性能PCIe载板开发实战指南 在当今高速数据处理领域,FPGA因其并行计算能力和可重构特性成为关键器件。Xilinx UltraScale系列的XCVU3P芯片配合FMC扩展接口,为开发者提供了强大的硬件加速平台。本文将深入解析如何从零开始构建一个支持…...
夺回社交主动权:iBeebo如何让微博回归纯粹体验
夺回社交主动权:iBeebo如何让微博回归纯粹体验 【免费下载链接】iBeebo 第三方新浪微博客户端 项目地址: https://gitcode.com/gh_mirrors/ib/iBeebo 你是否经历过这样的时刻?通勤路上想快速刷几条微博,却被开屏广告耽误了上车时间&am…...
手柄硬件校准与操控优化:从故障排查到竞技级设置的实战手册
手柄硬件校准与操控优化:从故障排查到竞技级设置的实战手册 【免费下载链接】DS4Windows Like those other ds4tools, but sexier 项目地址: https://gitcode.com/gh_mirrors/ds/DS4Windows 在《艾尔登法环》的 boss 战中,角色总是不受控制地缓慢…...
告别SIFT/ORB!用LoFTR+Transformer搞定低纹理场景的图片匹配(附Python实战代码)
低纹理场景图像匹配实战:LoFTR与Transformer的革新应用 在计算机视觉领域,图像特征匹配一直是三维重建、视觉定位等任务的基础环节。传统方法如SIFT、ORB依赖于特征检测器提取关键点,但在低纹理、重复图案或运动模糊场景中表现往往不尽如人意…...
手把手教你用丹青识画:智能影像雅鉴系统保姆级入门教程
手把手教你用丹青识画:智能影像雅鉴系统保姆级入门教程 1. 认识丹青识画系统 "以科技之眼,点画意之睛。"这句话完美诠释了丹青识画系统的核心理念。这是一款将人工智能技术与东方美学相结合的创新工具,能够自动分析图像内容并生成…...
【Python张量计算实战宝典】:20年AI架构师亲授5大高频场景优化技巧,错过再等一年
第一章:张量计算基础与PyTorch/TensorFlow双框架选型指南张量是深度学习的核心数据结构,本质为多维数组,支持自动微分、GPU加速与动态/静态计算图构建。理解其内存布局(如C-contiguous vs. Fortran-contiguous)、广播机…...
Qwen3-32B-Chat API优化:降低OpenClaw任务Token消耗的5个技巧
Qwen3-32B-Chat API优化:降低OpenClaw任务Token消耗的5个技巧 1. 为什么需要关注Token消耗? 当我第一次在本地部署OpenClaw对接Qwen3-32B-Chat模型时,最让我震惊的不是它的推理能力,而是执行简单自动化任务后Token消耗的速度。一…...
若依框架二次开发避坑指南:手把手教你定制菜品管理系统
若依框架二次开发实战:从零构建餐饮管理系统的高效避坑手册 当接到基于若依框架开发餐饮管理系统的任务时,很多开发者会陷入"能用但不好用"的困境。本文将分享我在三个不同规模餐饮项目中积累的实战经验,重点解析那些官方文档不会告…...
