单调栈

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

1. java复制代码
2.         import java.util.ArrayList;  
4.         import java.util.Stack;  
6.           
8.         public class MonotonicStack {  
10.             private Stack<Integer> stack;  
12.             private Stack<Integer> maxStack;  
14.           
16.             public MonotonicStack() {  
18.                 stack = new Stack<>();  
20.                 maxStack = new Stack<>();  
22.             }  
24.           
26.             public void push(int val) {  
28.                 if (val >= stack.peek()) {  
30.                     stack.push(val);  
32.                 } else {  
34.                     while (!maxStack.isEmpty() && val > maxStack.peek()) {  
36.                         maxStack.pop();  
38.                     }  
40.                     stack.push(val);  
42.                     maxStack.push(val);  
44.                 }  
46.             }  
48.           
50.             public int pop() {  
52.                 if (!stack.isEmpty()) {  
54.                     return stack.pop();  
56.                 } else {  
58.                     return -1;  
60.                 }  
62.             }  
64.           
66.             public int top() {  
68.                 if (!stack.isEmpty()) {  
70.                     return stack.peek();  
72.                 } else {  
74.                     return -1;  
76.                 }  
78.             }  
80.           
82.             public boolean isEmpty() {  
84.                 return stack.isEmpty();  
86.             }  
88.         }

复制代码

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

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