Monostack：找邻居助手

Next Greater Element

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

Bob说：“你看，我们从左往右一个个来看，对于每一个人来说，我们向前看第一个比TA高的就好了。“

Alice说：“那对于每一个人来说，都要比较与前面所有人的身高啊。怎么感觉有更快的方法？如果找到一个高个儿，TA不就是所有之前比TA矮的人的答案了吗？

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

模版如下[LC 739]：

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)时间的方法有可能是用单调栈来用空间换时间。

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

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 模式

给你一个整数数组 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())。不过由于单调栈的性质：最后弹出的数字相对最大，所以可以略去这个比较。

参考代码：

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