算法笔记

单调栈

单调栈是一种特殊的栈结构，它具有以下特点：

1. 单调递增栈：栈中元素从栈底到栈顶逐渐增大。当需要维护一个单调递增的序列时，可以使用单调递增栈。

2. 单调递减栈：栈中元素从栈底到栈顶逐渐减小。当需要维护一个单调递减的序列时，可以使用单调递减栈。

单调栈的主要用途包括：

1. 寻找元素的下一个更大元素（Next Greater Element）：对于给定的数组或序列，单调递增栈可以帮助我们快速找到每个元素的下一个比它大的元素，而单调递减栈则可以帮助我们找到每个元素的下一个比它小的元素。这个技巧在解决一些数组、链表等问题时非常有用。

2. 寻找元素的前一个更大元素（Previous Greater Element）：与上一条类似，但是方向相反。

3. 寻找元素的下一个更小元素（Next Smaller Element）：类似于寻找下一个更大元素，但是要维护一个单调递减栈。

4. 寻找元素的前一个更小元素（Previous Smaller Element）：类似于寻找前一个更大元素，但是要维护一个单调递减栈。

5. 求解柱状图中的最大矩形（Largest Rectangle in Histogram）：这个问题可以利用单调递增栈来求解，具体思路是遍历每个柱子，维护一个单调递增栈，对于每个柱子，计算以该柱子为高的最大矩形面积。

6. 求解接雨水问题（Trapping Rain Water）：这个问题也可以利用单调递减栈来求解，具体思路是维护一个单调递减栈，遍历每个柱子，如果当前柱子高度小于栈顶柱子高度，则将当前柱子入栈；如果当前柱子高度大于等于栈顶柱子高度，则出栈并计算雨水面积。

单调栈在解决这些问题时具有很好的效率和简洁性，能够通过栈结构的特性快速找到所需的信息，是算法中常用的重要工具之一。