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

数据结构 单调栈

应用情景

求当前元素 前面/后面,第一个比它 小/大 的元素的 值/下标/下标距离

优点

剔除重复寻路操作,将暴力 O(n^2) 优化到 O(n)

性质

从栈底开始,元素 单调递增/单调递减

单调性视具体情景而定 (找较大值还是较小值、找的方向)

思路

以某种形式存放遍历过的元素,使该种存放形式符合情景要求

讨论当前元素与栈顶元素比较大小后的几种情况分别对应什么操作

实现

按遍历顺序生成结果:

1.存放每一个遍历过的元素 (写在循环体最后)

2.对于当前元素,要知道有没有比它 大/小 的,就从栈顶向下找,不满足条件的直接出栈

因为对于之后还没遍历到的元素,栈顶不满足条件的元素和当前元素相比

一定劣于当前元素,不会再用到了

3.经历过 2. 之后,当前栈一定符合条件:若栈为空,则没有元素比当前元素更 小/大

若栈非空,则栈顶元素一定是第一个比当前元素 小/大 的

按其他顺序生成结果:略 (我遇到的题目都是按遍历顺序生成结果更优)

注意事项

注意讨论遍历方向,有时反着遍历,思路和代码更简洁

栈中元素有时候需要存数值,有时候要存下标,视题目要求而定

例题

LeetCode.739.每日温度

题目与题解:

题解 力扣 LeetCode 739 每日温度 C++-CSDN博客icon-default.png?t=O83Ahttps://blog.csdn.net/qwq_ovo_pwp/article/details/143243618?spm=1001.2014.3001.5501

相关文章:

数据结构 单调栈

应用情景 求当前元素 前面/后面,第一个比它 小/大 的元素的 值/下标/下标距离 优点 剔除重复寻路操作,将暴力 O(n^2) 优化到 O(n) 性质 从栈底开始,元素 单调递增/单调递减 单调性视具体情景而定 (找较大值还是较小值、找的方向) 思路…...

【NodeJS】NodeJS+mongoDB在线版开发简单RestfulAPI (七):MongoDB的设置

本项目旨在学习如何快速使用 nodejs 开发后端api,并为以后开展其他项目的开启提供简易的后端模版。(非后端工程师) 由于文档是代码写完之后,为了记录项目中需要注意的技术点,因此文档的叙述方式并非开发顺序&#xff0…...

基于flask和neo4j的医疗知识图谱展示问答系统

如果你仍在为毕业设计的选题发愁,或者想通过技术项目提升专业实力,这个基于Flask和Neo4j的医疗知识图谱展示与问答系统,绝对是个不错的选择! 项目亮点大揭秘: 知识图谱与问答结合:我们采用了医疗场景下的知…...

Python——脚本实现datax全量同步mysql到hive

文章目录 前言一、展示脚本二、使用准备1、安装python环境2、安装EPEL3、安装脚本执行需要的第三方模块 三、脚本使用方法1、配置脚本2、创建.py文件3、执行脚本4、测试生成json文件是否可用 前言 在我们构建离线数仓时或者迁移数据时,通常选用sqoop和datax等工具进…...

Python爬虫教程:从入门到精通

Python爬虫教程:从入门到精通 前言 在信息爆炸的时代,数据是最宝贵的资源之一。Python作为一种简洁而强大的编程语言,因其丰富的库和框架,成为了数据爬取的首选工具。本文将带您深入了解Python爬虫的基本概念、实用技巧以及应用…...

pytorh学习笔记——cifar10(四)用VGG训练

1、新建train.py,执行脚本训练模型: import os import timeimport torch import torch.nn as nn import torchvisionfrom vggNet import VGGbase, VGGNet from load_cifar import train_loader, test_loader import warnings import tensorboardX# 忽略…...

CRLF、UTF-8这些编辑器右下角的选项的意思

经常使用编辑器的小伙伴应该经常能看到右下角会有这么两个选项,下图是VScode中的示例,那么这两个到底是啥作用呢? 目录 字符编码ASCII 字符集GBK 字符集Unicode 字符集UTF-8 编码 换行 字符编码 此部分参考博文 在计算机中,所有…...

【C++干货篇】——类和对象的魅力(四)

【C干货篇】——类和对象的魅力(四) 1.取地址运算符的重载 1.1const 成员函数 将const修饰的成员函数称之为const成员函数,const修饰成员函数放到成员函数参数列表的后面。const实际修饰该成员函数隐含的this指针(this指向的对…...

基于java的诊所管理系统源码,SaaS门诊信息系统,二次开发的不二选择

门诊管理系统源码,诊所系统源码,saas服务模式 医疗信息化的新时代已经到来,诊所管理系统作为诊所管理和运营的核心工具,不仅提升了医疗服务的质量和效率,也为患者提供了更加便捷和舒适的就医体验,同时还推动…...

O2OA如何实现文件跨服务器的备份

O2OA可以外接存储服务器,但是一个存储服务器上怕磁盘损坏等问题导致文件丢失,所以需要实现文件跨服务器备份。 整体过程: 1、SSH免密登录配置 2、增加一个同步推送文件的.sh文件 3、编辑crontab 增加定时任务执行上一步的.sh文件 一、配…...

语音提示器-WT3000A离在线TTS方案-打破语种限制/AI对话多功能支持

前言: TTS(Text To Speech )技术作为智能语音领域的重要组成部分,能够将文本信息转化为逼真的语音输出,为各类硬件设备提供便捷的语音提示服务。本方案正是基于唯创知音的离在线TTS(离线本地音乐播放与在线…...

使用HAL库的STM32工程,实现DMA传输USART发送接收数据

以串口3为例,初始化部分为STM32CubeMX生成代码 串口初始化 UART_HandleTypeDef huart3; DMA_HandleTypeDef hdma_usart3_rx; DMA_HandleTypeDef hdma_usart3_tx;/* USART3 init function */ void MX_USART3_UART_Init(void) {/* USER CODE BEGIN USART3_Init 0 */…...

常用排序算法总结

内容目录 1. 选择类排序 1.1 直接选择排序1.2 堆排序 2. 交换类排序 2.1 冒泡排序2.2 快速排序 3. 插入类排序 3.1 直接插入排序3.2 希尔排序 4. 其它排序 4.1 归并排序4.2 基数排序/桶排序 排序 1. 选择类排序 选择类排序的特征是每次从待排序集合中选择出一个最大值或者最…...

[项目详解][boost搜索引擎#2] 建立index | 安装分词工具cppjieba | 实现倒排索引

目录 编写建立索引的模块 Index 1. 设计节点 2.基本结构 3.(难点) 构建索引 1. 构建正排索引(BuildForwardIndex) 2.❗构建倒排索引 3.1 cppjieba分词工具的安装和使用 3.2 引入cppjieba到项目中 倒排索引代码 本篇文章,我们将继续项…...

R语言编程

一、R语言在机器学习中的优势 R语言是一种广泛用于统计分析和数据可视化的编程语言,在机器学习领域也有诸多优势。 丰富的包:R拥有大量专门用于机器学习的包。例如,caret包是一个功能强大的机器学习工具包,它提供了统一的接口来训练和评估多种机器学习模型,如线性回归、决…...

Mysql主主互备配置

在现有运行的mysql环境下,修改相关配置项,完成主主互备模式的部署。 下面的配置说明中设置的mysql互备对应服务器IP为: 192.168.1.6 192.168.1.7 先检查UUID 在mysql的数据目录下,检查主备mysql的uuid(如下的server-…...

如何预防数据打架?数据仓库如何保持指标数据一致性开发指南(持续更新)

大数据开发人员最经常遇到尴尬和麻烦的事是,指标开发好了,以为万事大吉了。被业务和运营发现这个指标在不同地方数据打架,显示不同的数值。为了保证指标数据一致性,要从整个开发流程做好。 目录 一、数据仓库架构规划 二、数据抽取与转换 三、数据存储管理 四、指标管…...

我谈Canny算子

在Canny算子的论文中,提出了好的边缘检测算子应满足三点:①检测错误率低——尽可能多地查找出图像中的实际边缘,边缘的误检率(将边缘识别为非边缘)低,且避免噪声产生虚假边缘(将非边缘识别为边缘…...

算法的学习笔记—平衡二叉树(牛客JZ79)

😀前言 在数据结构中,二叉树是一种重要的树形结构。平衡二叉树是一种特殊的二叉树,其特性是任何节点的左右子树高度差的绝对值不超过1。本文将介绍如何判断一棵给定的二叉树是否为平衡二叉树,重点关注算法的时间复杂度和空间复杂度…...

SSM学习day01 JS基础语法

一、JS基础语法 跟java有点像,但是不用注明数据类型 使用var去声明变量 特点1:var关键字声明变量,是为全局变量,作用域很大。在一个代码块中定义的变量,在其他代码块里也能使用 特点2:可以重复定义&#…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

python打卡day49

知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

<6>-MySQL表的增删查改

目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表&#xf…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...