# Monostack：找邻居助手

## Next Greater Element

假设一队人前后站在一起，每个人向前看，由于前面的高个儿挡住了视线，所以只能看到自己和那个歌高个儿之间的同学。问题来了：**如何能快速知道每个人前面挡住视线的第一个高个儿呢？**于是有了这样的对话：

> Bob说：“你看，我们从左往右一个个来看，对于每一个人来说，我们向前看第一个比TA高的就好了。“
>
> Alice说：“那对于每一个人来说，都要比较与前面所有人的身高啊。怎么感觉有更快的方法？如果找到一个高个儿，TA不就是所有之前比TA矮的人的答案了吗？

这种把“**之前比TA矮的人**“存下来的数据结构就是单调栈。

**模版如下\[**[**LC 739**](https://leetcode-cn.com/problems/daily-temperatures)**]：**

```python
stack = []
for n in nums:
    while stack and n>stack[-1]:
        m = stack.pop() # m的nextGreater是n
    stack.append(n)
```

## 单调栈

单调栈利用了“先入后出“的原则方便我们来寻找`nextGreaterElement`或是`nextSmallerElement`。有些题要在数组中找对子，单个枚举可能要O(n²)，如果要寻找O(n)时间的方法有可能是用单调栈来用空间换时间。

![](https://3265673997-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MY_rO03Mc0ssTMstQFR%2F-MYpHt3UBlZr7IM9t_i8%2F-MYqIX-4T_x0XvDoMz_9%2FScreen%20Shot%202021-04-21%20at%202.20.13%20PM.png?alt=media\&token=5d30631c-42c4-4630-84cd-687d7f014257)

有时候需要把index存下来，来找到`nextGreaterElement`的等待时间。

```python
stack = []
for i, n in enumerate(nums):
    while stack and n>stack[-1][1]:
        j, m = stack.pop() # m等到nextGreater要i-j
    stack.append((i, n))
```

## 例题：[132 模式](https://leetcode-cn.com/problems/132-pattern/)

```python
给你一个整数数组 nums ，数组中共有 n 个整数。
132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，
并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。
```

我们把数字反转，就变成了寻找231模式。那么从左到右，我们可以用单调递减栈保存2和3。题目只要求寻找是否存在231模式，那么我们利用单调递减栈的性质：**所有弹出的数字都比栈中的数字小**，把“3“存在栈中，弹出的数字是“2“。我们反向遍历数组，然后看到有比存在的弹出数字更小的“1“，就找到了答案。

下面`mmax=stack.pop()`本也可以写作`mmax=max(mmax, stack.pop())`。不过由于单调栈的性质：**最后弹出的数字相对最大**，所以可以略去这个比较。

**参考代码：**

```python
def find132pattern(nums):
    stack = []           # has number "3"
    mmax = float('-inf') # number "2"
    for n in nums[::-1]: # look for number "1"
        if n < mmax: return True
        while stack and n > stack[-1]:
            mmax = stack.pop()
        stack.append(n)
    return False
```