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