ToB企服应用市场:ToB评测及商务社交产业平台

标题: 单调栈 [打印本页]

作者: 丝 时间: 2023-9-3 22:34
标题: 单调栈
单调栈是一种特殊的数据结构，它由栈内元素构成单调递增或单调递减的特性。具体来说，对于单调递增栈，栈内元素从栈底到栈顶单调递增；对于单调递减栈，栈内元素从栈底到栈顶单调递减。
单调栈的应用非常广泛，包括字符串匹配、路径寻找、序列比对等场景。
例如，在字符串匹配中，我们可以使用单调栈来优化暴力匹配算法。具体来说，我们使用单调递减栈存储文本串中尚未匹配的字符，保证栈底是文本串中最早出现的尚未匹配的字符。然后，对于模式串中的每个字符，我们依次与栈顶元素进行匹配。如果匹配成功，则将该字符压入栈中；如果匹配失败，则将栈顶元素弹出，相当于将该字符“忽略”。通过这种方式，我们可以快速找到模式串在文本串中的所有出现位置。
除了字符串匹配，单调栈还可以应用于其他场景。例如，在路径寻找问题中，我们可以使用单调递增栈来存储每个节点的后继节点。具体来说，我们将当前节点的后继节点依次压入栈中，并保证栈内元素按照到达当前节点的距离进行排序。然后，对于每个新到达的节点，我们可以从栈顶找到距离该节点最近的祖先节点，并以此为起点继续搜索。通过这种方式，我们可以快速找到从起点到终点的最短路径。
总之，单调栈是一种非常实用的数据结构，它可以广泛应用于各种场景。
单调栈是一种特殊的数据结构，用于解决一些特定的问题。以下是使用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 是否为空。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)