456. 132 模式
题目描述
输入整数数组 nums。
若存在三个下标 i < j < k，使得 nums[i] < nums[k] < nums[j]，就称数组中含有 132 模式：先小，再最大，最后取中间值。三个元素不必相邻。
存在这样的三元组返回 true，否则返回 false。
示例 1
输入：nums = [1,2,3,4] 输出：false
解释：数组严格递增，找不到 132 形状。
示例 2
输入：nums = [3,1,4,2] 输出：true
解释：[1,4,2] 构成 132 模式。
示例 3
输入：nums = [-1,3,2,0] 输出：true
解释：例如 [-1,3,2] 就满足条件。
数据范围
n == nums.length1 <= n <= 2 * 10^5-10^9 <= nums[i] <= 10^9
解题思路：前缀最小值 + 单调栈
枚举中间的“3” nums[j]。“1”要尽量小，取左边前缀最小值 mn[j]。问题变成：右边有没有一个数落在 (mn[j], nums[j]) 开区间内。从右往左扫，用栈保存右侧的候选“2”。对当前 j，先把栈中 <= mn[j] 的数弹掉；由于 mn 往左只会变大或不变，这些数以后也不可能大于“1”，弹掉不亏。栈顶就是右侧 > mn[j] 的最小数，它 < nums[j] 就找到了。否则把 nums[j] 压栈。这相当于在右侧有序集合里“二分查找第一个 > mn[j] 的数”，单调栈把这次查找摊还成 O(1)。
为什么正确
栈从底到顶严格递减（非增）；处理 j 时，栈中都是下标大于 j 的数，弹栈后都 > mn[j]。
复杂度分析
每个数至多入栈、出栈一次，时间 O(n)，空间 O(n)。若用有序列表 + 二分，则是 O(n log n)。
易错点
弹栈条件是 <= mn[j]（等于也要弹），因为要求严格 nums[i] < nums[k]。nums[j] <= mn[j] 时（它就是前缀最小）不能当“3”，直接跳过，也不压栈。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
n = len(nums)
mn = [0] * n
mn[0] = nums[0]
for i in range(1, n):
mn[i] = min(mn[i - 1], nums[i])
st = []
for j in range(n - 1, 0, -1):
if nums[j] > mn[j]:
while st and st[-1] <= mn[j]:
st.pop()
if st and st[-1] < nums[j]:
return True
st.append(nums[j])
return Falseclass Solution {
public boolean find132pattern(int[] nums) {
int n = nums.length;
int[] mn = new int[n];
mn[0] = nums[0];
for (int i = 1; i < n; i++) {
mn[i] = Math.min(mn[i - 1], nums[i]);
}
int[] st = new int[n]; int top = 0;
for (int j = n - 1; j > 0; j--) {
if (nums[j] > mn[j]) {
while (top > 0 && st[top - 1] <= mn[j]) {
top--;
}
if (top > 0 && st[top - 1] < nums[j]) {
return true;
}
st[top++] = nums[j];
}
}
return false;
}
}class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
vector<int> mn(n, 0);
mn[0] = nums[0];
for (int i = 1; i < n; i++) {
mn[i] = min(mn[i - 1], nums[i]);
}
vector<int> st;
for (int j = n - 1; j > 0; j--) {
if (nums[j] > mn[j]) {
while (!st.empty() && st.back() <= mn[j]) {
st.pop_back();
}
if (!st.empty() && st.back() < nums[j]) {
return true;
}
st.push_back(nums[j]);
}
}
return false;
}
};func find132pattern(nums []int) bool {
n := len(nums)
mn := make([]int, n)
mn[0] = nums[0]
for i := 1; i < n; i++ {
mn[i] = min(mn[i-1], nums[i])
}
st := []int{}
for j := n - 1; j > 0; j-- {
if nums[j] > mn[j] {
for len(st) > 0 && st[len(st)-1] <= mn[j] {
st = st[:len(st)-1]
}
if len(st) > 0 && st[len(st)-1] < nums[j] {
return true
}
st = append(st, nums[j])
}
}
return false
}var find132pattern = function(nums) {
const n = nums.length;
const mn = new Array(n).fill(0);
mn[0] = nums[0];
for (let i = 1; i < n; i++) {
mn[i] = Math.min(mn[i - 1], nums[i]);
}
const st = [];
for (let j = n - 1; j > 0; j--) {
if (nums[j] > mn[j]) {
while (st.length && st[st.length - 1] <= mn[j]) {
st.pop();
}
if (st.length && st[st.length - 1] < nums[j]) {
return true;
}
st.push(nums[j]);
}
}
return false;
};function find132pattern(nums: number[]): boolean {
const n = nums.length;
const mn: number[] = new Array(n).fill(0);
mn[0] = nums[0];
for (let i = 1; i < n; i++) {
mn[i] = Math.min(mn[i - 1], nums[i]);
}
const st: number[] = [];
for (let j = n - 1; j > 0; j--) {
if (nums[j] > mn[j]) {
while (st.length && st[st.length - 1] <= mn[j]) {
st.pop();
}
if (st.length && st[st.length - 1] < nums[j]) {
return true;
}
st.push(nums[j]);
}
}
return false;
}其他解法
主解法枚举“3”，用前缀最小值当“1”、单调栈找“2”；备选解法枚举“1”，用单调栈维护最大的“2”，更简洁但更难证明。
解法 2：单调栈（枚举 1，维护最大的 2） 时间 O(n)，空间 O(n)
从右往左扫描，维护一个从底到顶递减的单调栈，变量 k 表示目前能充当“2”的最大值。对每个 x：若 x < k，x 就能充当“1”，返回 true。否则把 x 当作“3”，弹出栈中所有比它小的元素，它们都能当“2”，k 取最后弹出的那个（最大）。最后把 x 入栈。
一次扫描，不需要前缀最小值数组，代码很短。正确性的关键是“k 只增不减”，不如枚举 3 的写法直观。
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
# 从右往左枚举 i（充当 "1"）；k 是已出现过的、可以充当 "2" 的最大值
k = -math.inf
st = [] # 单调栈，从底到顶递减
for x in reversed(nums):
if x < k:
return True
# x 充当 "3"：比它小的栈顶都可以当 "2"，取最后弹出的（最大的）
while st and st[-1] < x:
k = st.pop()
st.append(x)
return Falseclass Solution {
public boolean find132pattern(int[] nums) {
long k = Long.MIN_VALUE;
int[] st = new int[nums.length];
int top = 0;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] < k) return true;
while (top > 0 && st[top - 1] < nums[i]) {
k = st[--top];
}
st[top++] = nums[i];
}
return false;
}
}class Solution {
public:
bool find132pattern(vector<int>& nums) {
long long k = LLONG_MIN;
vector<int> st;
for (int i = (int)nums.size() - 1; i >= 0; i--) {
if (nums[i] < k) return true;
while (!st.empty() && st.back() < nums[i]) {
k = st.back();
st.pop_back();
}
st.push_back(nums[i]);
}
return false;
}
};func find132pattern(nums []int) bool {
k := math.MinInt64
st := []int{}
for i := len(nums) - 1; i >= 0; i-- {
if nums[i] < k {
return true
}
for len(st) > 0 && st[len(st)-1] < nums[i] {
k = st[len(st)-1]
st = st[:len(st)-1]
}
st = append(st, nums[i])
}
return false
}var find132pattern = function(nums) {
let k = -Infinity;
const st = [];
for (let i = nums.length - 1; i >= 0; i--) {
if (nums[i] < k) return true;
while (st.length && st[st.length - 1] < nums[i]) k = st.pop();
st.push(nums[i]);
}
return false;
};function find132pattern(nums: number[]): boolean {
let k = -Infinity;
const st: number[] = [];
for (let i = nums.length - 1; i >= 0; i--) {
if (nums[i] < k) return true;
while (st.length && st[st.length - 1] < nums[i]) k = st.pop()!;
st.push(nums[i]);
}
return false;
}