首页 > 其他分享 >单调栈

单调栈

时间:2023-09-03 11:34:11浏览次数:26  
标签:maxStack 元素 栈顶 节点 stack 单调

单调栈是一种特殊的数据结构,它由栈内元素构成单调递增或单调递减的特性。具体来说,对于单调递增栈,栈内元素从栈底到栈顶单调递增;对于单调递减栈,栈内元素从栈底到栈顶单调递减。

单调栈的应用非常广泛,包括字符串匹配、路径寻找、序列比对等场景。

例如,在字符串匹配中,我们可以使用单调栈来优化暴力匹配算法。具体来说,我们使用单调递减栈存储文本串中尚未匹配的字符,保证栈底是文本串中最早出现的尚未匹配的字符。然后,对于模式串中的每个字符,我们依次与栈顶元素进行匹配。如果匹配成功,则将该字符压入栈中;如果匹配失败,则将栈顶元素弹出,相当于将该字符“忽略”。通过这种方式,我们可以快速找到模式串在文本串中的所有出现位置。

除了字符串匹配,单调栈还可以应用于其他场景。例如,在路径寻找问题中,我们可以使用单调递增栈来存储每个节点的后继节点。具体来说,我们将当前节点的后继节点依次压入栈中,并保证栈内元素按照到达当前节点的距离进行排序。然后,对于每个新到达的节点,我们可以从栈顶找到距离该节点最近的祖先节点,并以此为起点继续搜索。通过这种方式,我们可以快速找到从起点到终点的最短路径。

总之,单调栈是一种非常实用的数据结构,它可以广泛应用于各种场景。
单调栈是一种特殊的数据结构,用于解决一些特定的问题。以下是使用Java实现单调栈的示例代码:

java复制代码
	import java.util.ArrayList;  

	import java.util.Stack;  

	  

	public class MonotonicStack {  

	    private Stack<Integer> stack;  

	    private Stack<Integer> maxStack;  

	  

	    public MonotonicStack() {  

	        stack = new Stack<>();  

	        maxStack = new Stack<>();  

	    }  

	  

	    public void push(int val) {  

	        if (val >= stack.peek()) {  

	            stack.push(val);  

	        } else {  

	            while (!maxStack.isEmpty() && val > maxStack.peek()) {  

	                maxStack.pop();  

	            }  

	            stack.push(val);  

	            maxStack.push(val);  

	        }  

	    }  

	  

	    public int pop() {  

	        if (!stack.isEmpty()) {  

	            return stack.pop();  

	        } else {  

	            return -1;  

	        }  

	    }  

	  

	    public int top() {  

	        if (!stack.isEmpty()) {  

	            return stack.peek();  

	        } else {  

	            return -1;  

	        }  

	    }  

	  

	    public boolean isEmpty() {  

	        return stack.isEmpty();  

	    }  

	}

在上面的代码中,我们使用了两个栈,stack 用于存储普通元素,maxStack 用于存储最大元素。在 push() 方法中,我们首先判断要插入的元素是否大于等于栈顶元素,如果是,则直接将其压入 stack 中;否则,我们将从 maxStack 中弹出比当前元素小的元素,直到找到一个比当前元素大的元素或 maxStack 为空。然后将当前元素压入 stack 中,并压入 maxStack 中。在 pop() 和 top() 方法中,我们直接从 stack 中弹出或返回栈顶元素。在 isEmpty() 方法中,我们判断 stack 是否为空。

标签:maxStack,元素,栈顶,节点,stack,单调
From: https://www.cnblogs.com/codingggo/p/17674795.html

相关文章

  • Leetcode刷题笔记——单调性
    单调性单调性是数学中使用的一种常见性质,通常用于描述函数,在高等数学中的定义常常为:设函数f(x)在区间I上有定义,如果对于I上的任意两个数x1和x2,当x1<x2时,有f(x1)<f(x2)(或者f(x1)>f(x2)),则称函数f(x)在区间I上是单调递增的(或者单调递减的)。例如如下图像就是两个单调函数。利用单......
  • [算法学习笔记][刷题笔记] 单调队列优化 dp
    前置知识·单调队列单调队列顾名思义,一般用于解决滑动RMQ问题。它的原理非常简单。我们维护一个双端队列,这个双端队列只维护可能成为区间最值的元素。最基础的单调队列,例如滑动窗口。直接依据题意维护即可。这里提供单调队列模板(STLdeque版)单调队列模板(STLdeque版)......
  • 逆向 | 简单调试器检测&调试器进程检测、虚拟机进程检测、启动路径检测、计算机名检测
    逆向|简单调试器进程检测、虚拟机进程检测、启动路径检测、计算机名检测写在自己书里的代码,丢一份到blog。简单调试器检测:#include<stdio.h>#include<windows.h>//定义枚举值constintProcessDebugPort=0x7;constintProcessDebugObjectHandle=0x1e;constint......
  • 【单调队列】 单调队列的“扫描线”理解
    【单调队列】单调队列的“扫描线”理解  “如果一个选手比你小还比你强,你就可以退役了。”——单调队列的原理比你强,而且比你影响时间更长。某种意义上,数学思维是生活中的思考的延伸。  算法学习笔记(66):单调队列。引用Pecco的算法笔记。  在这里给出一种扫描线......
  • 代码随想录算法训练营第十三天|单调数列:滑动窗口最大值(力扣239.)、优先级队列:前k个高
    单调数列:滑动窗口最大值(力扣239.)给定滑动窗口的范围,求每个滑动窗口范围内的最大值使用单调队列实现对于最大值数字前面的数字不存入数列,对于最大值数字后面的数字存入数列中单调队列中数字的大小呈递减顺序pop(value):如果窗口移除的元素等于单调队列的队口元素,则pop;否则什......
  • 单调栈(查找一个最大差值或查询某个位置左右两侧比他大(或小)的数的位置)
    leetcode121.买卖股票的最佳时机classSolution{public:intmaxProfit(vector<int>&prices){intans=0;vector<int>St;prices.emplace_back(-1);//为了结果的必然出现for(inti=0;i<prices.size();++i){......
  • 单调队列模板
    好的,这是一个晴朗的夜晚。-苯荏水平不高甚至菜亖,博客仅仅写给自己避免自己忘记学了什么,也仅据我理解写出,不严谨,非常不严谨。单调队列。在原序列基础上,维护一个单调的序列。单调队列中的元素在原序列中的相对位置不变,且在单调队列中的元素是单调的。基本模板题:https://www.lu......
  • LeetCode 周赛上分之旅 #39 结合中心扩展的单调栈贪心问题
    ⭐️本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]和BaguTreePro知识星球提问。学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场LeetCode周赛的解题报告,一......
  • [第358场周赛]分解质因数+单调栈+快速幂
    最近有点水逆,希望厄运赶快退散,一会会去祈福的。这场周赛依旧是3题遗憾离场,第4题经过提示其实涉及的算法都会但是实在是emmmm过于综合。7023. 操作使得分最大提示困难10相关企业给你一个长度为 n 的正整数数组 nums 和一个整数 k 。一开始,你的分数为 1 。你可以进行以下操......
  • 7937: 良好的感觉 单调栈
    描述 kkk做了一个人体感觉分析器。每一天,人都有一个感受值Ai,Ai 越大,表示人感觉越舒适。在一段时间[i,j] 内,人的舒适程度定义为[i,j] 中最不舒服的那一天的感受值×[i,j]中每一天感受值的和。现在给出kkk在连续N 天中的感受值,请问,在哪一段时间,kkk感觉最舒适? ......