LeetCode 456 - 132 模式

摘要

LeetCode 456 是一道乍一看很绕，但想通后非常优雅的题。

很多人第一次读题时，脑子里会立刻冒出三层循环：
找i < j < k，再判断nums[i] < nums[k] < nums[j]。
但很快你就会发现，这样做在数据量稍微大一点时，根本跑不动。

这道题真正考的是：
你能不能把“132 关系”转换成一种顺序扫描 + 单调结构的问题。

一旦理解了这一点，这题就会从“看不懂”变成“非常巧”。

描述

题目给你一个整数数组nums，让你判断数组中是否存在一种特殊的子序列，叫132 模式。

什么是 132 模式？

存在三个下标i < j < k，满足：

nums[i] < nums[k] < nums[j]

也就是说：

• 第一个数最小
• 第二个数最大
• 第三个数夹在中间

只要存在任意一组，直接返回true，否则返回false。

题解答案（整体思路）

为什么这题不适合正着想？

如果你从左往右去想：

• 固定j
• 去左边找最小的i
• 再去右边找合适的k

你会发现状态太多，逻辑也很难压缩。

这道题真正舒服的解法是：

从右往左看，用栈维护“可能成为 3 的值”，同时动态记录“可能成为 2 的最大值”。

核心思路一句话版

• 从右向左遍历数组
• 用一个单调递减栈保存“可能的 3（nums[j]）”
• 用一个变量third记录“已经找到的最大 nums[k]”
• 一旦发现nums[i] < third，说明 132 成立

题解答案（Swift 可运行 Demo）

classSolution{funcfind132pattern(_nums:[Int])->Bool{ifnums.count<3{returnfalse}varstack:[Int]=[]varthird=Int.min// 从右往左遍历fornuminnums.reversed(){// 如果当前数比 third 小，说明找到了 132ifnum<third{returntrue}// 维护单调递减栈whileletlast=stack.last,num>last{third=last stack.removeLast()}stack.append(num)}returnfalse}}

题解代码分析

这段代码短，但信息密度非常高，我们一步一步拆。

1. 为什么要从右往左？

fornuminnums.reversed(){

原因很关键：

• 我们希望先确定nums[j]和nums[k]
• 再回头看有没有更小的nums[i]

如果你从左往右，很难“记住未来的信息”。

2. 栈里存的到底是什么？

varstack:[Int]=[]

这个栈里存的是：

还没被淘汰的、可能作为 nums[j]（3 的位置）的值

而且这个栈始终保持单调递减。

3. third 是干嘛的？

varthird=Int.min

third表示：

目前已经确认的，最大可能的 nums[k]（2 的位置）

它来自哪里？

whileletlast=stack.last,num>last{third=last stack.removeLast()}

当你发现当前数num比栈顶大时：

• 说明num可以作为更大的3
• 被弹出的那个数，就成了“被夹在中间的 2”

4. 核心判断为什么是这样？

ifnum<third{returntrue}

此时的含义是：

• 当前num是nums[i]
• third是已经找到的nums[k]
• 而之前一定存在一个更大的nums[j]

自然满足：

nums[i] < nums[k] < nums[j]

132 模式成立。

示例测试及结果

示例 1

letsolution=Solution()print(solution.find132pattern([1,2,3,4]))

输出：

false

解释：

• 数组严格递增
• 永远找不到中间被夹住的值

示例 2

print(solution.find132pattern([3,1,4,2]))

输出：

true

解释：

• 子序列[1,4,2]
• 完整满足 132 模式

示例 3

print(solution.find132pattern([-1,3,2,0]))

输出：

true

解释：

• 存在多组 132
• 算法只要找到一组就会提前返回

实际场景结合

这道题的思想，在现实中非常常见。

1. 时间序列异常检测

比如股票价格：

• 先涨
• 再回落一点
• 但仍高于早期低点

这本质就是一种 132 模式。

2. 指标反转识别

在监控系统中：

• 指标低
• 突然拉高
• 又回落到中间区间

这类“先拉高再回调”的结构，本质和 132 一样。

3. 为什么栈思路很重要？

因为它能把：

• “多点关系”
• “跨区间比较”

压缩成一次线性扫描。

这是工程里非常值钱的能力。

时间复杂度

• 每个元素最多进栈、出栈一次

时间复杂度：

O(n)

空间复杂度

• 使用了一个栈

空间复杂度：

O(n)

总结

LeetCode 456 是一道非常典型的“思路型”题目：

• 不是靠暴力
• 不是靠技巧堆叠
• 而是靠换一个观察角度