单调栈分类、封装和总结
作者推荐
map|动态规划|单调栈|LeetCode975:奇偶跳
通过枚举最小(最大)值不重复、不遗漏枚举所有子数组
| C++算法:美丽塔O(n)解法单调栈 | 左右寻找第一个小于maxHeight[i]的left,right,[left,right]直接的高度都是maxHeight[i] 可以用封装的类,可以理解为枚举山顶这个子数组 |
| 【单调栈]LeetCode84: 柱状图中最大的矩形 | |
| 【单调栈】【区间合并】LeetCode85:最大矩形 | |
| 【单调栈】LeetCode2334:元素值大于变化阈值的子数组 | |
| 【单调栈】LeetCode:2818操作使得分最大 | |
| 【前缀和】【单调栈】LeetCode2281:巫师的总力量和 | |
| map 动态规划 单调栈 LeetCode975:奇偶跳 |
封装类
class CRangIndex
{
public:template<class _Pr>CRangIndex(int iVectorSize, _Pr CurIndexCmpStackTopIndex){m_c = iVectorSize;m_vLeft.assign(m_c, -1);m_vRight.assign(m_c, m_c);stack<int> sta;for (int i = 0; i < m_c; i++){while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top()))){m_vRight[sta.top()] = i;sta.pop();}if (sta.size()){m_vLeft[i] = sta.top();}sta.emplace(i);}}template<class _Pr>CRangIndex(const vector<int>& nums, _Pr CurValueCmpStackTopValue){m_c = nums.size();m_vLeft.assign(m_c, -1);m_vRight.assign(m_c, m_c);stack<int> sta;for (int i = 0; i < m_c; i++){while (sta.size() && (CurValueCmpStackTopValue(nums[i], nums[sta.top()]))){m_vRight[sta.top()] = i;sta.pop();}if (sta.size()){m_vLeft[i] = sta.top();}sta.emplace(i);}}int m_c;vector<int> m_vLeft, m_vRight;//vLeft[i] 从右向左第一个小于nums[i] ;vRight[i] 是第一个小于等于nums[i]。
};
测试用例
大于
CRangIndex ri(nums, std::greater<>()); 结果:右边界从左向右第一个大于当前值,左边界从右向左第一个大于等于当前值
| 原数组 | 左边界 | 右边界 |
|---|---|---|
| 1 2 3 3 4 | -1 -1 -1 2 -1 | 1 2 4 4 5 |
| 8 7 3 4 | -1 0 1 1 | 4 4 3 4 |
大于等于
CRangIndex ri(nums, std::greater_equal<>());
结果:右边界从左向右第一个大于等于当前值,左边界从右向左第一个大于当前值
.|原数组 | 左边界 | 右边界|
|–|–|–|
1 2 3 3 4|-1 -1 -1 -1 -1|1 2 3 4 5
8 7 3 4| -1 0 1 1|4 4 3 4
小于
CRangIndex ri(nums, std::less<>());
结果:右边界从左向右第一个小于当前值,左边界从右向左第一个小于等于当前值
.|原数组 | 左边界 | 右边界|
|–|–|–|
1 2 3 3 4|-1 0 1 2 3|5 5 5 5 5
8 7 3 4 |-1 -1 -1 2|1 2 4 4
小于等于
CRangIndex ri(nums, std::less_equal<>());
结果:右边界从左向右第一个小于等于当前值,左边界从右向左第一个小于当前值
.|原数组 | 左边界 | 右边界|
1 2 3 3 4|-1 0 1 1 3|5 5 3 5 5
8 7 3 4| -1 -1 -1 2|1 2 4 4
int main()
{vector<int> nums;{nums = { 1,2,3,3,4 };CRangIndex ri(nums, std::less_equal<>());std::cout << "数组值:";CConsole::Out(nums);std::cout << "左边界:";CConsole::Out(ri.m_vLeft);std::cout << "左边界:";CConsole::Out(ri.m_vRight);}{nums = { 8,7,3,4 };CRangIndex ri(nums, std::less_equal<>());std::cout << "数组值:";CConsole::Out(nums);std::cout << "左边界:";CConsole::Out(ri.m_vLeft);std::cout << "左边界:";CConsole::Out(ri.m_vRight);}
}
二分查找的进一步优化
| 子状态都单调递增或单调递减 |
| 一,插入也是有序,直接栈顶插入。二,淘汰无效状态后,直接栈顶插入。 |
| 二,要查询的值是被淘汰的元素。二,要查询的值是栈顶元素。 |
【单调栈】LeetCode1776:车队
【单调栈】LeetCode:1944队列中可以看到的人数
最小(最大)字典序
【单调栈 】LeetCode321:拼接最大数
【单调栈】LeetCode2030:含特定字母的最小子序列
其它
| 【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV | |
| 【map】【单调栈 】LeetCode768: 最多能完成排序的块 II |

扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用C++ 实现。

相关文章:
单调栈分类、封装和总结
作者推荐 map|动态规划|单调栈|LeetCode975:奇偶跳 通过枚举最小(最大)值不重复、不遗漏枚举所有子数组 C算法:美丽塔O(n)解法单调栈左右寻找第一个小于maxHeight[i]的left,right,[left,right]直接的高度都是maxHeight[i] 可以…...
【Amazon 实验①】使用 Amazon CloudFront加速Web内容分发
文章目录 实验架构图1. 准备实验环境2. 创建CloudFront分配、配置动、静态资源分发2.1 创建CloudFront分配,添加S3作为静态资源源站2.2 为CloudFront分配添加动态源站 在本实验——使用CloudFront进行全站加速中,将了解与学习Amazon CloudFront服务&…...
<math.h> 头文件:C语言数学库函数
文章目录 概述基本算术运算sqrt()fabs()pow() 三角函数sin()cos() 对数函数log()log10() 指数函数exp() 其他函数ceil()floor() 结语 概述 math.h 是C语言标准库中的头文件,提供了许多与数学运算相关的函数。在本文中,我们将深入讨论一些 math.h 中常用…...
1.CentOS7网络配置
CentOS7网络配置 查看网络配置信息 ip addr 或者 ifconfig 修改网卡配置信息 vim /etc/sysconfig/network-scripts/ifcfg-ens192 设备类型:TYPEEthernet地址分配模式:BOOTPROTOstatic网卡名称:NAMEens192是否启动:ONBOOTye…...
Prompt-to-Prompt:基于 cross-attention 控制的图像编辑技术
Hertz A, Mokady R, Tenenbaum J, et al. Prompt-to-prompt image editing with cross attention control[J]. arXiv preprint arXiv:2208.01626, 2022. Prompt-to-Prompt 是 Google 提出的一种全新的图像编辑方法,不同于任何传统方法需要用户指定编辑区域ÿ…...
搭载紫光展锐芯的移远通信RedCap模组顺利通过中国联通OPENLAB实验室认证
近日,移远通信联合紫光展锐在中国联通5G物联网OPENLAB开放实验室,完成了RedCap模组RG207U-CN端到端测试验收,并获颁认证证书。移远通信RG207U-CN成为业内率先通过联通OPENLAB认证的紫光展锐RedCap芯片平台的模组。 本次测试基于联通OPENLAB实…...
16-高并发-队列术
队列,在数据结构中是一种线性表,从一端插入数据,然后从另一端删除数据。 在我们的系统中,不是所有的处理都必须实时处理,不是所有的请求都必须实时反馈结果给用户,不是所有的请求都必须100%一次性处理成功…...
【设计模式-2.5】创建型——建造者模式
说明:本文介绍设计模式中,创建型设计模式中的最后一个,建造者模式; 入学报道 创建型模式,关注于对象的创建,建造者模式也不例外。假设现在有一个场景,高校开学,学生、教师、职工都…...
VideoPoet: Google的一种用于零样本视频生成的大型语言模型
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
pytest常用命令行参数
文章目录 一、前置说明二、操作步骤1. 命令行中执行:pytest2. 命令行中执行:pytest - v3. 命令行中执行:pytest -s4. 命令行中执行:pytest -k test_addition5. 命令行中执行:pytest -k test_pytest_command_params.py6. 命令行中执行:pytest -v -s -k test_pytest_comman…...
05. Springboot admin集成Actuator(一)
目录 1、前言 2、Actuator监控端点 2.1、健康检查 2.2、信息端点 2.3、环境信息 2.4、度量指标 2.5、日志文件查看 2.6、追踪信息 2.7、Beans信息 2.8、Mappings信息 3、快速使用 2.1、添加依赖 2.2、添加配置文件 2.3、启动程序 4、自定义端点Endpoint 5、自定…...
AI生成SolidUI-新版本架构调试Debug
背景 SolidUI 0.5.0 版本重构全新版本架构。 dev-python 新架构临时分支,架构调整完后,所有代码合并到dev分支 https://github.com/CloudOrc/SolidUI 使用 设置参数 FLASK_DEBUG 设置 在开发过程中,Web框架的服务器通常会监视代码的变…...
ctfshow sql 195-200
195 堆叠注入 十六进制 if(preg_match(/ |\*|\x09|\x0a|\x0b|\x0c|\x0d|\xa0|\x00|\#|\x23|\|\"|select|union|or|and|\x26|\x7c|file|into/i, $username)){$ret[msg]用户名非法;die(json_encode($ret));}可以看到没被过滤,select 空格 被过滤了,可…...
微信小程序实现地图功能(腾讯地图)
微信小程序实现地图功能(腾讯地图) 主要功能 通过微信 API 获取用户当前位置信息 使用腾讯地图 API 将经纬度转换为地址信息 显示当前位置信息以及周围的 POI(兴趣点) 代码实现 index.wxml <!-- index.wxml --> <view class"container&…...
Vue如何请求接口——axios请求
1、安装axios 在cmd或powershell打开文件后,输入下面的命令 npm install axios 可在项目框架中的package.json中查看是否: 二、引用axios import axios from axios 在需要使用的页面中引用 三、get方式使用 get请求使用params传参,本文只列举常用参数…...
【数据结构一】初始Java集合框架(前置知识)
Java中的数据结构 Java语言在设计之初有一个非常重要的理念便是:write once,run anywhere!所以Java中的数据结构是已经被设计者封装好的了,我们只需要实例化出想使用的对象,便可以操作相应的数据结构了,本篇…...
直接将第三方数据插入到 Redis 中
Redis 是一个内存数据库,可以用于缓存和持久化数据。虽然常见的使用场景是将数据从关系型数据库(如MySQL)同步到 Redis 中进行缓存,但也可以直接将第三方数据插入到 Redis 中。 你可以通过编程语言的 Redis 客户端库(…...
【重点】【DP】322.零钱兑换
题目 法1:动态规划 // 时间复杂度:O(kN) class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount 1];Arrays.fill(dp, amount 1);dp[0] 0;for (int i 1; i < dp.length; i) {for (int coin : coins) {if (…...
Python入门学习篇(六)——for循环while循环
1 for循环 1.1 常规for循环 1.1.1 语法结构 for 变量名 in 可迭代对象:# 遍历对象时执行的代码 else:# 当for循环全部正常运行完(没有报错和执行break)后执行的代码1.1.2 示例代码 print("----->学生检查系统<------") student_lists["张三",&qu…...
el-table 实现行拖拽排序
element ui 表格实现拖拽排序的功能,可以借助第三方插件Sortablejs来实现。 引入sortablejs npm install sortablejs --save组件中使用 import Sortable from sortablejs;<el-table ref"el-table":data"listData" row-key"id" …...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...
