456. 132模式

链接

https://leetcode.cn/problems/132-pattern/description/

思路

这题其实不难，就是边界条件难想。

我们可以先保证单调栈里是逆序，然后判断单调栈中较小的值是否大于当前元素（满足132的1和2的关系）。

代码

class Solution:
    def find132pattern(self, nums) -> bool:
        # 初始化单调栈
        single_stack = []
        # last_maxs暂存为第二大的值, 初始化为一个极小值, 这样好把数据刷到last_maxs中
        last_maxs = float("-inf")
        # 倒着遍历, 我们需要一个逆序的单调栈, 因为132, 我们需要求32 所以应该是逆序的
        for i in nums[::-1]:
            # 如果当前值小于第二大的值, 即满足了132, 那么就可以判定为True
            if i < last_maxs:
                return True
            # 逆序, 所以栈顶小于当前值的要弹栈
            while single_stack and single_stack[-1] < i:
                # 更新倒数第二大的值, 倒数第二大的值越大, 我们越有可能满足132, 所以可以放心的去求max
                # 并且，while 循环满足的条件是, 栈顶元素小于当前元素, 所以我们还有当前元素兜底, 随便max更新即可
                last_maxs = max(last_maxs, single_stack[-1])
                single_stack.pop()
            # 这条语句起到2条作用
            # 第一, 初始化single_stack
            # 第二, 如第二大的数比当前值还小, 那显然不满足, 证明i就是当前栈里最大的值了, 将i入栈。
            if last_maxs < i:
                single_stack.append(i)
        return False