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

# \[456]\[中等]\[栈] 132模式

## 题目描述

[456. 132 模式](https://leetcode-cn.com/problems/132-pattern/)

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

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

进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？

示例 1：

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

示例 2：

```
输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
```

示例 3：

```
输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
```

提示：

* n == nums.length
* 1 <= n <= 104
* -109 <= nums\[i] <= 109

## 解题思路

注意到`132`模式中, 3是其中最大的数字, 且2还要比1大. 本题的关键, 是以3为划分点, 在左侧和右侧分别找出合适的1和2.

如果从左向右遍历, 记录维护3的位置, 如果使用当前位置左侧的最大值作为3, 数组中的132模式很可能出现在后面, 如`[0, 4, -3, -1, -2]`, 如果以元素4为`132`模式中的3, 就无法找到正确的132子序列`[-3, -1, -2]`.

换句话说, 1和3作为`132`模式中的最小值和最大值, 如果维护这两个值, 只会让他们之间的空间越来越大, 而真正的`132`模型在这个空间中出现的概率就越来越大.

所以有效的做法是维护2, 因为2是1和3之间的中间值, 如果1<2并且2<3, 根据传递性得到1<3. 我们从右向左遍历, 遇到的每一个元素, 都可能是最后的2, 即2的候选元素. 在它们遇到一个更大的元素后, 才能成为真正的2.

首先将最右侧的元素作为2的候选元素, 压入栈中. 在遍历下一个元素时, 如果新元素更小, 栈中的元素是没有资格成为真正的2的, 这个元素也要压入到栈中, 成为候选. 换个角度, 遇到一个新元素, 栈中所有小于这个元素的2的候选元素, 都具备了称为真正2的资格, 我们将栈顶所有小于新元素的元素弹出, **这些被弹出的元素都是可以真正作为2的**. 我们再使用一个变量`max_second`, 记录所有被弹出元素的最大值, 这样有:

* 我们维护了一个2的候选元素栈, 且这个栈是**单调递减栈**, 因为更小的值被直接压入栈, 更大的值需要弹出比它小的值才会被压入栈
* 真正称为真正2的元素都被弹出, 栈中存在的值只是候选, 因为它们的左侧没有大于它们的值
* 我们只使用一个变量, 记录真正的2, 且只记录最大值. 无需记录3, 因为每个被弹出的值, 具有了真正是2的资格后, 就不再需要它对应的3了, 只需要寻找它对应的1即可
* 只记录真正的2的最大值, 是因为2越大, 留给1的空间就越大

因此, 继续遍历:

* 如果新元素小于`max_second`, 而`max_second`是具有2资格的元素, 肯定存在一个比它大的3, 因此我们就找到了一个结果, 直接返回`True`
* 对于新元素, 将其与栈顶元素比较, 如果它严格大于栈顶元素, 将栈顶元素弹出, 并将弹出的元素与`max_second`比较, 记录最大的具有2资格的元素. 重复这个过程直到栈为空, 或新元素不再大于栈顶元素, 将新元素压入栈
* 有个优化点, 如果新元素小于`max_second`, 它弹出的元素肯定也不会大于当前的`max_second`. 而如果我们还把这个元素压入栈, 后面被弹出时也不会对`max_second`产生影响, 因此这个新元素没有必要被压入栈中

最后代码如下:

```python
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False

        stack = [nums[-1]]
        max_second = float('-inf')

        for i in range(n - 2, -1, -1):
            if nums[i] < max_second:
                return True

            while stack and nums[i] > stack[-1]:
                max_second = max(stack.pop(), max_second)

            if nums[i] > max_second:
                stack.append(nums[i])

        return False
```

## 参考资料

* [132模式](https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/)
* [栈解法 超详细题解](https://leetcode-cn.com/problems/132-pattern/solution/zhan-jie-fa-chao-xiang-xi-ti-jie-by-siyy/)
* [【相信科学系列】详解为何使用「单调栈」来找最大的 K 是正确的 ...](https://leetcode-cn.com/problems/132-pattern/solution/xiang-xin-ke-xue-xi-lie-xiang-jie-wei-he-95gt/)