注意：这里定义的顺序是从「栈顶」到「栈底」。有的文章里是反过来的。本文全文以「栈顶」到「栈底」的顺序为基准来描述单调栈。

单调递增栈的入栈、出栈过程如下：

- 假设当前进栈元素为 $x$，如果 $x$ 比栈顶元素小，则直接入栈。

- 否则从栈顶开始遍历栈中元素，把小于 $x$ 或者等于 $x$ 的元素弹出栈，直到遇到一个大于 $x$ 的元素为止，然后再把 $x$ 压入栈中。

下面我们以数组 $[2, 7, 5, 4, 6, 3, 4, 2]$ 为例，模拟一下「单调递增栈」的进栈、出栈过程。具体过程如下：

- 数组元素：$[2, 7, 5, 4, 6, 3, 4, 2]$，遍历顺序为从左到右。

| 第 i 步 | 待插入元素 | 操 作 | 结 果（左侧为栈底） | 作 用 |

| :-----: | :--------: | ---------------------- | ------------------- | ------------------------------------- |

| 1 | 2 | 2 入栈 | [2] | 元素 2 的左侧无比 2 大的元素 |

| 2 | 7 | 2 出栈，7 入栈 | [7] | 元素 7 的左侧无比 7 大的元素 |

| 3 | 5 | 5 入栈 | [7, 5] | 元素 5 的左侧第一个比 5 大的元素为：7 |

| 4 | 4 | 4 入栈 | [7, 5, 4] | 元素 4 的左侧第一个比 4 大的元素为：5 |

| 5 | 6 | 4 出栈，5 出栈，6 入栈 | [7, 6] | 元素 6 的左侧第一个比 6 大的元素为：7 |

| 6 | 3 | 3 入栈 | [7, 6, 3] | 元素 3 的左侧第一个比 3 大的元素为：6 |

| 7 | 4 | 3 出栈，4 入栈 | [7, 6, 4] | 元素 4 的左侧第一个比 4 大的元素为：6 |

| 8 | 2 | 2 入栈 | [7, 6, 4, 2] | 元素 2 的左侧第一个比 2 大的元素为：4 |

最终栈中元素为 $[7, 6, 4, 2]$。因为从栈顶（右端）到栈底（左侧）元素的顺序为 $2, 4, 6, 7$，满足递增关系，所以这是一个单调递增栈。

我们以上述过程第 5 步为例，所对应的图示过程为：

单调递减栈的入栈、出栈过程如下：

- 假设当前进栈元素为 $x$，如果 $x$ 比栈顶元素大，则直接入栈。

- 否则从栈顶开始遍历栈中元素，把大于 $x$ 或者等于 $x$ 的元素弹出栈，直到遇到一个小于 $x$ 的元素为止，然后再把 $x$ 压入栈中。

下面我们以数组 $[4, 3, 2, 5, 7, 4, 6, 8]$ 为例，模拟一下「单调递减栈」的进栈、出栈过程。具体过程如下：

- 数组元素：$[4, 3, 2, 5, 7, 4, 6, 8]$，遍历顺序为从左到右。

| 第 i 步 | 待插入元素 | 操 作 | 结 果（左侧为栈底） | 作用 |

| :-----: | :--------: | ---------------------- | ------------------- | ------------------------------------- |

| 1 | 4 | 4 入栈 | [4] | 元素 4 的左侧无比 4 小的元素 |

| 2 | 3 | 4 出栈，3 入栈 | [3] | 元素 3 的左侧无比 3 小的元素 |

| 3 | 2 | 3 出栈，2 入栈 | [2] | 元素 2 的左侧无比 2 小的元素 |

| 4 | 5 | 5 入栈 | [2, 5] | 元素 5 的左侧第一个比 5 小的元素是：2 |

| 5 | 7 | 7 入栈 | [2, 5, 7] | 元素 7 的左侧第一个比 7 小的元素是：5 |

| 6 | 4 | 7 出栈，5 出栈，4 入栈 | [2, 4] | 元素 4 的左侧第一个比 4 小的元素是：2 |

| 7 | 6 | 6 入栈 | [2, 4, 6] | 元素 6 的左侧第一个比 6 小的元素是：4 |

| 8 | 8 | 8 入栈 | [2, 4, 6, 8] | 元素 8 的左侧第一个比 8 小的元素是：6 |

最终栈中元素为 $[2, 4, 6, 8]$。因为从栈顶（右端）到栈底（左侧）元素的顺序为 $8, 6, 4, 2$，满足递减关系，所以这是一个单调递减栈。

我们以上述过程第 6 步为例，所对应的图示过程为：

单调栈可以在时间复杂度为 $O(n)$ 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。

所以单调栈一般用于解决一下几种问题：

- 寻找左侧第一个比当前元素大的元素。

- 寻找左侧第一个比当前元素小的元素。

- 寻找右侧第一个比当前元素大的元素。

- 寻找右侧第一个比当前元素小的元素。

下面分别说一下这几种问题的求解方法。

- 从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：

- 一个元素左侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。

- 如果插入时的栈为空，则说明左侧不存在比当前元素大的元素。

- 从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：

- 一个元素左侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。

- 如果插入时的栈为空，则说明左侧不存在比当前元素小的元素。

- 从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：

- 一个元素右侧第一个比它大的元素就是将其「弹出单调递增栈」时即将插入的元素。

- 如果该元素没有被弹出栈，则说明右侧不存在比当前元素大的元素。

- 从右到左遍历元素，构造单调递增栈（从栈顶到栈底递增）：

- 一个元素右侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。

- 如果插入时的栈为空，则说明右侧不存在比当前元素大的元素。

- 从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：

- 一个元素右侧第一个比它小的元素就是将其「弹出单调递减栈」时即将插入的元素。

- 如果该元素没有被弹出栈，则说明右侧不存在比当前元素小的元素。

- 从右到左遍历元素，构造单调递减栈（从栈顶到栈底递减）：

- 一个元素右侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。

- 如果插入时的栈为空，则说明右侧不存在比当前元素小的元素。

上边的分类解法有点绕口，可以简单记为以下条规则：

- 无论哪种题型，都建议从左到右遍历元素。

- 查找 **「比当前元素大的元素」** 就用 **单调递增栈**，查找 **「比当前元素小的元素」** 就用 **单调递减栈**。

- 从 **「左侧」** 查找就看 **「插入栈」** 时的栈顶元素，从 **「右侧」** 查找就看 **「弹出栈」** 时即将插入的元素。

for num in nums: