本文档全面解释了单调栈数据结构，包括其属性、实现和在算法问题求解中的常见应用。单调栈代表了一种高级技术，通常在掌握了基本数据结构和中级算法之后学习，正如存储库的学习路径所示。本页面仅关注单调栈；有关相关的栈操作，请参阅栈和队列。
单调栈是一种特殊的栈数据结构，它维护栈中元素的单调顺序（严格递增或严格递减）。与仅强制执行后进先出（LIFO）行为的常规栈不同，单调栈对栈中元素的相对值增加了额外的约束。
关键属性是，在压入新元素时，我们首先移除会破坏单调属性的现有元素，然后再压入新元素。
单调递增栈确保元素从栈底到栈顶是升序排列的。压入新元素时，弹出所有大于或等于新元素的元素。
单调递减栈确保元素从栈底到栈顶是降序排列的。压入新元素时，弹出所有小于或等于新元素的元素。
单调栈通过修改压栈行为扩展了标准的栈接口
| 操作 | 描述 | 单调递增栈 | 单调递减栈 |
|---|---|---|---|
| 推送 | 添加元素 | 先弹出所有较大的元素 | 先弹出所有较小的元素 |
| 弹栈（Pop） | 移除栈顶 | 与普通栈相同 | 与普通栈相同 |
| 查看栈顶 | 查看栈顶 | 与普通栈相同 | 与普通栈相同 |
| isEmpty | 检查是否为空 | 与普通栈相同 | 与普通栈相同 |
C++ 中单调栈的实现通常遵循以下模式
1. Initialize an empty stack
2. For each element in the input array:
a. While stack is not empty AND current element violates monotonic property with stack.top():
- Process the popped element (often the key step for solving the problem)
- Pop from stack
b. Push current element (and possibly its index) onto stack
3. Process any remaining elements in the stack if needed
单调栈特别适用于高效解决特定类型的问题
最常见的应用之一是查找数组中每个元素的下一个更大（或更小）的元素。
问题示例：下一个更大元素 I (496)
给定两个数组，找出第一个数组中每个元素在第二个数组中的下一个更大元素。
来源：README.md368
对于循环数组，我们通常处理两次以处理回绕情况。
问题示例：下一个更大元素 II (503)
查找循环数组中每个元素的下一个更大元素。
来源：README.md369
单调栈可以解决诸如接雨水和查找直方图中最大矩形等复杂问题。
问题示例：接雨水 (42)
计算不同高度的柱子之间能容纳多少水。
来源：README.md370
问题要求找出每天需要等待多少天才能遇到更暖和的天气。
单调栈方法:
来源：README.md367
找出直方图中最大的矩形面积。
单调栈方法:
来源：README.md371
// Pseudocode for monotonically increasing stack
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] >= arr[i]) {
// Process the element being popped
st.pop();
}
// Optional: process current element with respect to stack
st.push(i);
}
// Pseudocode for monotonically decreasing stack
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] <= arr[i]) {
// Process the element being popped
st.pop();
}
// Optional: process current element with respect to stack
st.push(i);
}
考虑使用单调栈的情况包括：
| 数据结构 | 何时选择单调栈 |
|---|---|
| 普通栈 | 仅需要 LIFO 行为时 |
| 队列 | 需要 FIFO 行为时 |
| 优先队列 | 当需要整个集合中的最小/最大元素时 |
| 线段树 | 当需要对静态数组进行范围查询时 |
单调栈是一种强大的技术，可以高效地解决特定类型的问题，特别是那些涉及查找下一个更大/更小元素或计算直方图面积的问题。关键在于，通过维护单调属性，我们可以高效地在一次数据遍历中处理元素，从而使原本可能需要 O(n²) 时间的朴素方法在特定问题领域达到 O(n) 的时间复杂度。
这种高级数据结构建立在基础栈操作之上，并展示了专门的约束如何能够显著优化特定问题域的算法。