【题目描述】
给你一个整数数组nums，数组中共有
n
n
n个整数。
132
132
132模式的子序列由三个整数nums[i]、nums[j]和nums[k]组成，并同时满足：
i
<
j
<
k
i
【示例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
=
=
n
u
m
s
.
l
e
n
g
t
h
n==nums.length
n==nums.length
1
≤
n
≤
2
∗
1
0
5
1le nle 2*10^5
1≤n≤2∗105
−
1
0
9
≤
n
u
m
s
[
i
]
≤
1
0
9
-10^9le nums[i]le 10^9
−109≤nums[i]≤109
【分析】
我们可以从右往左遍历数组考虑每个数作为 1 1 1或 3 3 3的情况，同时维护一个次大值，这个次大值满足左边有一个数比它大，即是 132 132 132模式中的 2 2 2。假如我们遇到了小于当前次大值的数说明我们就找到了一个 1 1 1，构成了一个 132 132 132模式。否则我们就把当前数看成 3 3 3，从当前数开始向右找到比当前数小的数并且更新次大值，这里我们只用向右找到第一个比当前数大的位置 x x x即可，因为从 x x x开始再往右的数如果小于当前数那么它也一定会小于这个比当前数大的数 x x x，也就是说他们之前已经在考虑 x x x的时候被作为次大值更新过了，没有必要再重新更新一遍。
我们从右往左扫描数组并维护一个单调递减的栈，初始时次大值设为无穷小。
如果当前数小于次大值说明我们找到了一个答案，否则考虑当前数作为 3 3 3的情况。
如果当前数大于栈顶时说明我们找到了一个 32 32 32模式，我们不断的弹出栈顶来更新 2 2 2，即维护我们当前遇到的次大值，直到栈顶大于当前值为止，此时 r i g h t right right记录了右边第一个比它大的元素之前，比它小的最大的数（比较绕，大家可以仔细斟酌）。
注意这时栈顶的右边可能还有之前被弹出过的小于当前数的值，但他们都会比当前的 2 2 2小，即在扫描过程中这个 2 2 2是会单调递增的，原因是如果不是单调递增的，那么这个第一次出现下降的数和当前的栈顶以及栈顶右边的数就构成了一个 132 132 132模式，会在之前就直接返回。
【代码】
class Solution {
public:
bool find132pattern(vector& nums) {
int right = -1e9;//right表示nums[i]右边第一个比它大的元素左边的比nums[i]小的元素的最大值
stack stk;
for (int i = nums.size() - 1; i >= 0; i--)
{
if (nums[i] < right) return true;
while (stk.size() && nums[i] > stk.top())
right = max(right, stk.top()), stk.pop();
stk.push(nums[i]);
}
return false;
}
};
//复制一遍防止篇幅过短QWQ
class Solution {
public:
bool find132pattern(vector& nums) {
int right = -1e9;//right表示nums[i]右边第一个比它大的元素左边的比nums[i]小的元素的最大值
stack stk;
for (int i = nums.size() - 1; i >= 0; i--)
{
if (nums[i] < right) return true;
while (stk.size() && nums[i] > stk.top())
right = max(right, stk.top()), stk.pop();
stk.push(nums[i]);
}
return false;
}
};
