> For the complete documentation index, see [llms.txt](https://1425816423.gitbook.io/suan-fa-xiao-ce/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://1425816423.gitbook.io/suan-fa-xiao-ce/zhan/dan-diao-zhan.md).

# 单调栈

## 单调栈

### 单调栈的定义与作用

单调栈的定义可以用一句话描述：**单调递增或单调减的栈。单调栈是在执行的过程中不断的使栈变得单调，在这一过程中解决问题**，单调栈通常适用于解决下一个更大或者下一个更小的问题。

用一个例子来更好地展示单调栈：

**问题**

给定一个整数数组 `temperatures`，表示每天的温度，返回一个数组 `answer`，其中 `answer[i]`是指对于第 `i`天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 `0`来代替。

**思路1（暴力破解）**

这道题最简单直观地方法就是用两个`for`循环来查找，第一个`for`循环用`i`去扫描一遍`temperatures` ，第二个for循环去扫描`i` 到 `temperatures.length-1` ，直到找到第一个大于`temperatures[i]` 的元素或者到达终点。这种方法的时间复杂度是`O(n^2)` 。

**思路2（单调栈）**

换个思路，这道题是典型的”找到下一个更大的元素”，如果我们在遍历时维护一个单调递增的栈结构，这个栈中包含所有的未找到下一个更高温度的元素，那么每次循环时只要去判断当前元素`temperatures[i]` 是否比栈顶元素大就可以找到下一个更大的元素，

具体做法是第一层循环时将所有元素扔到这个栈中，每次循环时都去判断一下当前元素(`temperatures[i]`)是否大于栈顶元素，如果是，那么`temperatures[i]` 就是气温高于栈顶元素当前气温的那一天，栈顶元素出栈，然后下一个元素变为了栈顶元素，`temperatures[i]`继续栈顶元素比较，直到栈为空或者栈顶元素大于`temperatures[i]` ，然后将`temperatures[i]` 入栈。此时所有出栈的元素都找到了气温高于自身的天数，并且这个栈由于不断地比较与出栈，会一直保持单调递增的特性，如果到最后都没有遇到比其更大的元素，则说明`temperatures` 中没有比它们更大的元素，因此直接设置为0。

根据单调栈的特性，如果我们在第一层`for` 循环时能够维护一个**单调递增**的栈，栈顶元素就是从0到i-1中最大的元素，如果i能够大于栈顶元素，那么