# 0456. 132 模式
### 题目地址(456. 132 模式)
### 题目描述
```
给你一个整数数组 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
```
### 前置知识
* [单调栈](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/monotone-stack)
### 公司
* 暂无
### 思路
132 模式指的是满足：大小关系是 1 < 2 < 3 ，索引关系是 1 < 3 < 2 的三个数。
一个简单的思路是使用一层**从左到右**的循环固定 3，遍历的同时维护最小值，这个最小值就是 1（如果固定的 3 不等于 1 的话）。 接下来使用另外一个嵌套寻找枚举符合条件的 2 即可。 这里的符合条件指的是大于 1 且小于 3。这种做法的时间复杂度为 $O(n^2)$，并不是一个好的做法，我们需要对其进行优化。
实际上，我们也可以枚举 2 的位置，这样目标变为找到一个大于 2 的数和一个小于 2 的数。由于 2 在序列的右侧，因此我们需要**从右往左**进行遍历。又由于题目只需要找到一个 132 模式，因此我们应该贪心地选择尽可能大的 2（只要不大于 3 即可），这样才**更容易找到 1**（换句话说不会错过 1）。
首先考虑找到 32 模式。我们可以使用从右往左遍历的方式，当遇到一个比后一位大的数时，我们就找到了一个可行的 32 模式。
和上面思路类似，维护一个全局最小值即可，这样就不会错过答案。可是这样就无法做到前面提到的**贪心地选择尽可能大的 2**，我们选择的 2 实际上是尽可能小的 2。那如何找到尽可能大的并且比当前数（3）小的 2 呢？
其实，我们可以维护一个递增栈。每次遇到一个比栈顶大的数就 pop 栈，直到栈顶比当前数字还大。那么最后一次 pop 出去的就是满足条件的最大的 2 了。找到了 32 模式，接下来，我们只需要找到一个比 2 小的数就可以直接返回 True 了。
### 关键点
* 先找到 32 模式，再找 132 模式。
* 固定 2, 从右往左遍历,使用单调栈获取最大的小于当前数的 2，并将当前数作为 3 。
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def find132pattern(self, A: List[int]) -> bool:
stack = []
p2 = float("-inf")
for a in A[::-1]:
# p2 不为初始值意味着我们已经找到了 32 模式，因此 a < p2 时候，我们就找到了 132 模式
if a < p2:
return True
while stack and a > stack[-1]:
p2 = stack.pop()
stack.append(a)
return False
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/456.132-pattern.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.