456. 132 模式

难度中等

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

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

示例 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 <= 2 * 10^5
-10^9 <= nums[i] <= 10^9

# 枚举 1

由于是 132 模式，即： $ijk$

枚举下标 $i$ ，找到大于 $nums[i]$ 的元素下标 $k$ ，然后只需要在 $(i,k)$ 范围内找到大于 $nums[k]$ 的元素即可

由于 32 都在 1 的右边，所以应该倒序枚举 $i$

因为需要预先知道 1 后面的所有值

可以维护单调递减栈：顶 [0,3,4] 底

若 $nums[i] > peek$ ，则不断地弹出栈顶直至 $nusm[i] <= peek$ ，而弹出的最后一个元素即为 2 小于 3 的最大元素 nums[k]

此时栈顶元素即为 3 ，弹出的元素即为 2 ，必然有 2 小于 3

而 $nums[i]$ 即为 1 ，只需要检查 1 是否小于 2 即可，即： $nums[i] < k\quad?$

例如： $[0,1,4,2,3]$

$i=4,st:[]$ 。压入 $3$

$i=3,st:[3]$ 。压入 $2$

$i=2,st:[2,3]$

$nums[i] = 4 > peek = 2$ ，则弹出 $2$ 并更新最小元素 $k$ 为 $2$ ， $st:[3]$

$nums[i] = 4 > peek = 3$ ，则弹出 $3$ 并更新最小元素 $k$ 为 $3$ ， $st:[]$

压入 $4$

$i=1,st:[4]$

$nums[i]=1 < k = 3$ ，满足条件，返回 $true$

	class Solution {
	public boolean find132pattern(int[] nums) {
	int n = nums.length;
	// 递减栈
	Deque<Integer> st = new ArrayDeque<>();
	int k = Integer.MIN_VALUE;
	for (int i = n - 1; i >= 0; i--) {
	// 此时已然满足 `2` < `3`, 只需看 `1` < `2` ?
	if (nums[i] < k) {
	return true;
	}
	// 弹出栈顶元素直至 peek >= nums [i]
	while (!st.isEmpty() && st.peekFirst() < nums[i]) {
	k = st.pollFirst();
	}
	st.addFirst(nums[i]);
	}
	return false;
	}
	}

# 枚举 2

$ijk$

维护单调递减栈：底 [3,2,1] 顶。栈顶元素即为 3 ，枚举 $k$ 的同时需要尽可能地保证 3 大

$[3,5,0,3,4]$

若采用递增栈，在枚举到 $4$ 的时候， $st:[0,3]$ ，栈中只有 $0,3$ ，但需要的是 $5$

若 $nums[k] > peek$ ，不断地弹出栈顶元素直至 $nums[k] <= peek$ 。此时栈顶元素即为 3 ，只需要寻找 3 左边比 3 小的最小元素 1 并判断 1 是否满足 1 < 2 即可。

在枚举 $k$ 的同时维护 $k$ 左边比 $nums[k]$ 小的最小元素 1 ，因为 $j$ 必然在 $k$ 左边。

为什么此时栈顶元素即为 3 ，而不是栈顶下面的元素？，况且栈顶下面的元素更大于栈顶元素

若栈顶元素 3 不满足条件 l[peek] < nums[k] ，由于是递减栈，栈中元素必然大于等于栈顶元素， $l[peek]$ 必然小于等于栈顶元素，所以 $l[peek]$ 也必然小于等于栈中元素

况且栈顶元素都不满足条件，即： $l[peek] > nums[k]$ ，而栈中元素 $l[internal] > l[peek]$ ，所以 $l[internal] > nums[k]$ ，所以栈中元素也不会满足条件。

例如 $[1,3 ,1, 1]$

$i=3,st:[3,1]$

$l[peek]=1 == nums[k]$ ，不满足条件

$l[internal] =1 >= l[peek] = 1$ ，也必然不可能满足条件

	class Solution {
	public boolean find132pattern(int[] nums) {
	int n = nums.length;
	// 递减栈
	Deque<Integer> st = new ArrayDeque<>();
	//j 左边满足小于 nums [j] 的最小元素
	int[] l = new int[n];
	int mn = Integer.MAX_VALUE;
	// 枚举 k
	for (int k = 0; k < n; k++) {
	while (!st.isEmpty() && nums[st.peekFirst()] <= nums[k]) {
	st.pollFirst();
	}
	// 此时栈顶元素就是 `3`
	if (!st.isEmpty() && l[st.peekFirst()] < nums[k]) {
	return true;
	}
	l[k] = mn;
	mn = Math.min(mn, nums[k]);
	st.addFirst(k);
	}
	return false;
	}
	}

# 枚举 3

# 单调栈

$ijk$

枚举下标 $j$ ，找到小于 $nums[j]$ 的元素下标 $i$ ，找到大于 $nums[j]$ 的元素下标 $j$ ，需要满足 $nums[i] < nums[j]$

我们可以最小化 $nums[i]$ ，最大化 $nums[j]$

即： $j$ 左边小于 $nums[j]$ 的最小元素 $nums[i]$ ， $j$ 右边大于 $nums[j]$ 的最大元素 $nums[k]$

对于 $i$ ，可以预处理，计算 $nums[j]$ 的最小元素 $mn$ 即可
对于 $k$ ，可以维护一个自底向上的递减栈：顶 $[0, 3, 4]$ 底。从后往前遍历

若 $nums[j] > peek$ ，则不断地弹出栈顶元素直至 $nums[j] <= peek$ 。而弹出的最后一个栈顶元素即为「右边大于 $nums[j]$ 的最大元素 $nums[k]$ 」

最后比较 $mn$ 是否小于 $nums[k]$ 即可
$nums[j]$ 为 3 ，弹出的最后一个元素为 2 ，必然满足 3 > 2 ，此时只需要看 1 < 2 ? ，而 1 即为 $l[j]$

例如： $[3,1,4,2,3]$

$j=4,st:[]$ ，压入 $3$

$j=3,st:[3]$ ，压入 $2$

$j=2,st:[2,3]$
- $nums[i] = 4 > peek = 2$ ，则弹出 $2$ 并更新最小元素为 $2$ ， $st:[3]$
  
  $nums[i] = 4 > peek = 3$ ，则弹出 $3$ 并更新最小元素为 $3$ ， $st:[]$
  
  比较 $l[j]=1$ 与 $3$ 的大小

	class Solution {
	public boolean find132pattern(int[] nums) {
	int n = nums.length;
	//l : 左边小于 nums [i] 的最小元素
	int[] l = new int[n];
	l[0] = Integer.MAX_VALUE;
	int mn = nums[0];
	for (int i = 1; i < n; i++) {
	l[i] = mn;
	mn = Math.min(nums[i], mn);
	}
	// 递减栈
	Deque<Integer> st = new ArrayDeque<>();
	for (int j = n - 1; j >= 0; j--) {
	int k = -1;
	// 不断地弹栈直至栈顶元素大于 nums [j]
	while (!st.isEmpty() && nums[st.peekFirst()] < nums[j]) {
	k = st.pollFirst();
	}
	if (k != -1 && l[j] < nums[k]) {
	return true;
	}
	st.addFirst(j);
	}
	return false;
	}
	}

# 平衡树