题目描述
这是 LeetCode 上的「456. 132 模式」，难度为「中等」。
Tag : 「单调栈」
给你一个整数数组 nums，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：
和
。
如果 nums 中存在 132 模式的子序列 ，返回 true；否则，返回 false。
进阶：很容易想到时间复杂度为
的解决方案，你可以设计一个时间复杂度为
或
的解决方案吗？
示例 1：
代码语言：javascript复制输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。
示例 2：
代码语言：javascript复制输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。
示例 3：
代码语言：javascript复制输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
提示：
基本思路
朴素的做法是分别对三个数进行枚举，这样的做法是
的，数据范围是
，稳稳超时。
事实上，这样的数据范围甚至不足以我们枚举其中两个数，然后优化找第三个数的
做法。
这时候根据数据范围会联想到树状数组，使用树状数组的复杂度是
的，可以过。但是代码量会较多一点，还需要理解离散化等前置知识。题解也不太好写。
因此，我们可以从 132 的大小特性去分析，如果在确定一个数之后，如何快速找到另外两个数（我们使用 ijk 来代指 132 结构）：
- 枚举
i：由于i是 132 结构中最小的数，那么相当于我们要从 i 后面，找到一个对数(j,k)，使得(j,k)都满足比i大，同时j和k之间存在j > k的关系。由于我们的遍历是单向的，因此我们可以将问题转化为找k，首先k需要比i大，同时在[i, k]之间存在比k大的数即可。 - 枚举
j：由于j是 132 结构里最大的数，因此我们需要在j的右边中比j小的「最大」的数，在j的左边找比j小的「最小」的数。这很容易联想到单调栈，但是朴素的单调栈是帮助我们找到左边或者右边「最近」的数，无法直接满足我们「最大」和「最小」的要求，需要引入额外逻辑。 - 枚举
k：由于k是 132 结构中的中间值，这里的分析逻辑和「枚举 i」类似，因为遍历是单向的，我们需要找到k左边的i，同时确保[i,k]之间存在比i和k大的数字。
以上三种分析方法都是可行的，但「枚举 i」的做法是最简单的。
因为如果存在 (j,k) 满足要求的话，我们只需要找到一个最大的满足条件的 k，通过与 i 的比较即可。
也许你还不理解是什么意思。没关系，我们一边证明一边说。
过程 & 证明
先说处理过程吧，我们从后往前做，维护一个「单调递减」的栈，同时使用 k 记录所有出栈元素的最大值（k 代表满足 132 结构中的 2）。
那么当我们遍历到 i，只要满足发现满足 nums[i] < k，说明我们找到了符合条件的 i j k。
举个
