男的怎么做直播网站,龙元建设陕西公司网站,oa办公系统有哪些,深圳网站设计建设公司#x1f308;个人主页#xff1a;聆风吟 #x1f525;系列专栏#xff1a;算法模板、数据结构 #x1f516;少年有梦不应止于心动#xff0c;更要付诸行动。 文章目录 #x1f4cb;前言一. ⛳️单调栈讲解1.1 #x1f514;单调栈的定义1.2 #x1f514;如何维护一个单… 个人主页聆风吟 系列专栏算法模板、数据结构 少年有梦不应止于心动更要付诸行动。 文章目录 前言一. ⛳️单调栈讲解1.1 单调栈的定义1.2 如何维护一个单调栈1.3 单调栈的用途1.4 模板总结(重点)1.4 单调栈的实例练习 全文总结 前言 hello! 各位铁子们大家好哇今天作者给大家带来了单调栈的算法解密因为前面我们已经讲解了用数组模拟栈过程今天单调栈也是采用数组模拟在此就不多做叙述有需要补漏的小伙伴可以自行前往下面专栏去浏览。 系列专栏本期文章收录在《算法模板》大家有兴趣可以浏览和关注后面将会有更多精彩内容 欢迎大家关注点赞收藏⭐️留言 一. ⛳️单调栈讲解
1.1 单调栈的定义 定义栈内的元素是单调递增或单调递减的栈。 1.2 如何维护一个单调栈
单调递增栈在保持栈内元素单调递增的前提下如果栈顶元素大于要入栈的元素将栈顶元素弹出将新元素入栈。单调递减栈在保持栈内元素单调递减的前提下如果栈顶元素小于要入栈的元素则将栈顶元素弹出将新元素入栈。
1.3 单调栈的用途 由上图可以看出对于栈内元素来说 在栈内左边的数就是数组中左边第一个比自己小的元素但元素被弹出时遇到的就是数组中右边第一个比自己小的元素。 对于将要入栈的元素来说在对栈进行更新后即弹出了所有比自己大的元素此时栈顶元素就是数组中左侧第一个比自己小的元素 由上图可以看出对于栈内元素来说 在栈内左边的数就是数组中左边第一个比自己大的元素但元素被弹出时遇到的就是数组中右边第一个比自己大的元素。 对于将要入栈的元素来说在对栈进行更新后即弹出了所有比自己小的元素此时栈顶元素就是数组中左侧第一个比自己大的元素 由此我们可以看出单调栈的用途是给定一个序列指定一个序列中的元素求解该元素左侧或右侧第一个比自己小或大的元素。
1.4 模板总结(重点)
本文总结的模板是找出每个数左边离它最近的比它大或小的数右边的可以自行推导单看模板比较抽象建议看完下面的题目在返回来看
//常见模型找出每个数左边离它最近的比它大/小的数
int tt 0;//栈顶指针
for (int i 1; i n; i )
{//check函数是判断查找//1. 每个数左边第一个比它小的数//2. 还是每个数左边第一个比它大的数while (tt check(stk[tt], i)) tt -- ;stk[ tt] i;
}1.4 单调栈的实例练习
⌈ 在线OJ链接 ⌋
题目
输入样例 5 3 4 2 7 5 输出样例 -1 3 -1 2 2 解题思路 我们还是以上面的 3 4 2 7 5 来举例分析开始遍历 3 这个元素此时栈为空那就表明 3 这个元素左侧没有比自身小的元素将结果 -1 记录一下或者直接输出。然后将 3 压入栈中。遍历到 4 时发现 4 大于栈顶的元素 3表明 4 这个元素左侧第一个比自身小的元素是 3将结果 3 记录一下或者直接输出。遍历到 2 时发现 2 小于栈顶的元素 44 是不可能作为结果输出的所以需要将栈顶的 4 弹出。弹出之后栈顶的元素就是 3 同样 2 仍然小于 3需要再次将 3 弹出。此时我们发现栈里面已经没有元素了说明 2 的左侧没有比自身小的元素将结果 -1 记录一下。然后将 2 压入栈中。其他的元素同理便可以得出下面给出了动图这里就不一一讲解了
c代码
#include iostreamusing namespace std;
const int N 100010;
int stk[N], tt;int main()
{int n 0;cin n;for(int i 0; i n; i){int x 0;cin x;//如果栈顶元素大于当前待入栈元素则出栈while(tt stk[tt] x) tt--;if(tt){//栈顶元素就是左侧第一个比它小的元素。cout stk[tt] ;}else {//如果栈空则没有比该元素小的值。cout -1 ;}//将当前元素加入单调栈中stk[tt] x;}return 0;
}全文总结
本文主要讲解
单调栈的定义栈内的元素是单调递增或单调递减的栈如何维护一个单调栈单调栈的用途给定一个序列指定一个序列中的元素求解该元素左侧或右侧第一个比自己小或大的元素实例练习 文章可能会有出现错误的地方欢迎大家在评论区里指正非常感谢。同时希望大家课下能够多敲多练孰能生巧。 今天的内容就到这里了你对今天的内容是否有所掌握如果还有疑问的话请在评论区里多多提问大家可以一起帮你解决让我们共同进步。创作不易如果对你有用的的话点个赞支持下作者你们的支持是作者创作最大的动力。关注我不迷路让我们下期再见✋✋。
