文章目录
- 摘要
- 描述
- 题解答案（整体思路）
- 为什么这题不适合正着想？
- 核心思路一句话版
- 题解答案（Swift 可运行 Demo）
- 题解代码分析
- 1. 为什么要从右往左？
- 2. 栈里存的到底是什么？
- 3. third 是干嘛的？
- 4. 核心判断为什么是这样？
- 示例测试及结果
- 示例 1
- 示例 2
- 示例 3
- 实际场景结合
- 1. 时间序列异常检测
- 2. 指标反转识别
- 3. 为什么栈思路很重要？
- 时间复杂度
- 空间复杂度
- 总结
摘要
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.minthird表示：
目前已经确认的，最大可能的 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 是一道非常典型的“思路型”题目：
- 不是靠暴力
- 不是靠技巧堆叠
- 而是靠换一个观察角度
