单调栈

这篇文章介绍了单调栈，分享给大家做个参考，收藏Java资料网收获更多编程知识

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

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

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

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

总之，单调栈是一种非常实用的数据结构，它可以广泛应用于各种场景。
单调栈是一种特殊的数据结构，用于解决一些特定的问题。以下是使用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 是否为空。

文章来源:https://www.cnblogs.com/codingggo/p/17674795.html
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！