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

单调栈分类、封装和总结

作者推荐

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 -11 2 4 4 5
8 7 3 4-1 0 1 14 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:奇偶跳 通过枚举最小&#xff08;最大&#xff09;值不重复、不遗漏枚举所有子数组 C算法&#xff1a;美丽塔O(n)解法单调栈左右寻找第一个小于maxHeight[i]的left,right&#xff0c;[left,right]直接的高度都是maxHeight[i] 可以…...

【Amazon 实验①】使用 Amazon CloudFront加速Web内容分发

文章目录 实验架构图1. 准备实验环境2. 创建CloudFront分配、配置动、静态资源分发2.1 创建CloudFront分配&#xff0c;添加S3作为静态资源源站2.2 为CloudFront分配添加动态源站 在本实验——使用CloudFront进行全站加速中&#xff0c;将了解与学习Amazon CloudFront服务&…...

<math.h> 头文件:C语言数学库函数

文章目录 概述基本算术运算sqrt()fabs()pow() 三角函数sin()cos() 对数函数log()log10() 指数函数exp() 其他函数ceil()floor() 结语 概述 math.h 是C语言标准库中的头文件&#xff0c;提供了许多与数学运算相关的函数。在本文中&#xff0c;我们将深入讨论一些 math.h 中常用…...

1.CentOS7网络配置

CentOS7网络配置 查看网络配置信息 ip addr 或者 ifconfig 修改网卡配置信息 vim /etc/sysconfig/network-scripts/ifcfg-ens192 设备类型&#xff1a;TYPEEthernet地址分配模式&#xff1a;BOOTPROTOstatic网卡名称&#xff1a;NAMEens192是否启动&#xff1a;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 提出的一种全新的图像编辑方法&#xff0c;不同于任何传统方法需要用户指定编辑区域&#xff…...

搭载紫光展锐芯的移远通信RedCap模组顺利通过中国联通OPENLAB实验室认证

近日&#xff0c;移远通信联合紫光展锐在中国联通5G物联网OPENLAB开放实验室&#xff0c;完成了RedCap模组RG207U-CN端到端测试验收&#xff0c;并获颁认证证书。移远通信RG207U-CN成为业内率先通过联通OPENLAB认证的紫光展锐RedCap芯片平台的模组。 本次测试基于联通OPENLAB实…...

16-高并发-队列术

队列&#xff0c;在数据结构中是一种线性表&#xff0c;从一端插入数据&#xff0c;然后从另一端删除数据。 在我们的系统中&#xff0c;不是所有的处理都必须实时处理&#xff0c;不是所有的请求都必须实时反馈结果给用户&#xff0c;不是所有的请求都必须100%一次性处理成功…...

【设计模式-2.5】创建型——建造者模式

说明&#xff1a;本文介绍设计模式中&#xff0c;创建型设计模式中的最后一个&#xff0c;建造者模式&#xff1b; 入学报道 创建型模式&#xff0c;关注于对象的创建&#xff0c;建造者模式也不例外。假设现在有一个场景&#xff0c;高校开学&#xff0c;学生、教师、职工都…...

VideoPoet: Google的一种用于零样本视频生成的大型语言模型

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为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 新架构临时分支&#xff0c;架构调整完后&#xff0c;所有代码合并到dev分支 https://github.com/CloudOrc/SolidUI 使用 设置参数 FLASK_DEBUG 设置 在开发过程中&#xff0c;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));}可以看到没被过滤&#xff0c;select 空格 被过滤了&#xff0c;可…...

微信小程序实现地图功能(腾讯地图)

微信小程序实现地图功能(腾讯地图) 主要功能 通过微信 API 获取用户当前位置信息 使用腾讯地图 API 将经纬度转换为地址信息 显示当前位置信息以及周围的 POI&#xff08;兴趣点&#xff09; 代码实现 index.wxml <!-- index.wxml --> <view class"container&…...

Vue如何请求接口——axios请求

1、安装axios 在cmd或powershell打开文件后&#xff0c;输入下面的命令 npm install axios 可在项目框架中的package.json中查看是否&#xff1a; 二、引用axios import axios from axios 在需要使用的页面中引用 三、get方式使用 get请求使用params传参,本文只列举常用参数…...

【数据结构一】初始Java集合框架(前置知识)

Java中的数据结构 Java语言在设计之初有一个非常重要的理念便是&#xff1a;write once&#xff0c;run anywhere&#xff01;所以Java中的数据结构是已经被设计者封装好的了&#xff0c;我们只需要实例化出想使用的对象&#xff0c;便可以操作相应的数据结构了&#xff0c;本篇…...

直接将第三方数据插入到 Redis 中

Redis 是一个内存数据库&#xff0c;可以用于缓存和持久化数据。虽然常见的使用场景是将数据从关系型数据库&#xff08;如MySQL&#xff09;同步到 Redis 中进行缓存&#xff0c;但也可以直接将第三方数据插入到 Redis 中。 你可以通过编程语言的 Redis 客户端库&#xff08;…...

【重点】【DP】322.零钱兑换

题目 法1&#xff1a;动态规划 // 时间复杂度&#xff1a;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 表格实现拖拽排序的功能&#xff0c;可以借助第三方插件Sortablejs来实现。 引入sortablejs npm install sortablejs --save组件中使用 import Sortable from sortablejs;<el-table ref"el-table":data"listData" row-key"id" …...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...