企业官网建设流程全解析

• 教程
• 文档

本篇技术指南以 456. 132 模式（中等） 题解为核心，完整讲解如何利用「逆序遍历 + 单调递减栈」在 $O(n)$ 时间内判定数组中是否存在满足 $nums[i] < nums[k] < nums[j]$（$i < j < k$）的三元组。文中从朴素枚举的复杂度瓶颈出发，逐步推导出"维护单调递减栈 + 记录出栈元素最大值k"的核心算法，并给出过程演示、正确性证明以及 Java / C++ / Python3 / TypeScript 四种语言的完整可运行代码，读完后你将掌握一类"借助单调栈把三重枚举压缩为单趟扫描"的经典技巧，并能够直接迁移到 单调栈专题 中的其他同类题目。

一、题目回顾：什么是 132 模式

LeetCode456. 132 模式（中等）要求：给定一个整数数组nums，判断其中是否存在"132 模式"的子序列。

所谓132 模式，即存在三个下标 $i < j < k$，且数值满足：

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

从形状上看，这三个数的相对大小关系构成"1 → 3 → 2"的排列，因此得名。注意这里的子序列不要求连续，只需保持相对顺序即可。

示例解析

示例 1

输入：nums = [1,2,3,4] 输出：false

序列单调递增，任意三元组都满足 $nums[i] < nums[j] < nums[k]$，无法凑出"中间最大、末尾次大"的形态，因此不存在 132 模式。

示例 2

输入：nums = [3,1,4,2] 输出：true

子序列[1, 4, 2]满足 $1 < 2 < 4$，即 $i=1,\ j=2,\ k=3$ 对应 $nums[1]=1 < nums[3]=2 < nums[2]=4$，命中 132 模式。

示例 3

输入：nums = [-1,3,2,0] 输出：true

存在 3 组 132 模式的子序列：[-1, 3, 2]、[-1, 3, 0]和[-1, 2, 0]，因此返回true。

数据范围与进阶要求

• $n = nums.length$，且 $1 \le n \le 10^4$
• $-10^9 \le nums[i] \le 10^9$

进阶要求是设计时间复杂度为 $O(n \log n)$ 或 $O(n)$ 的算法——这直接决定了朴素做法不可行，也指明了本题的核心考点在于"如何压缩枚举维度"。

二、朴素思路与复杂度瓶颈

最直接的思路是分别枚举 $i$、$j$、$k$ 三个位置，逐一检查是否满足 $nums[i] < nums[k] < nums[j]$，复杂度为 $O(n^3)$。在 $n$ 最大为 $10^4$ 时，$10^{12}$ 量级的运算在 LeetCode 上必然超时。

更"折中"的做法是枚举其中两个数、再优化第三个数的查找：例如枚举 $i$ 与 $j$，然后在其后查找是否存在位于 $(nums[i], nums[j])$ 区间内的 $nums[k]$。若用哈希表辅助，可将单次查找降为 $O(1)$，整体为 $O(n^2)$。但正如题解原文所指出的：

这样的数据范围甚至不足以我们枚举其中两个数，然后优化找第三个数的 $O(n^2)$ 做法。

$n=10^4$ 时 $O(n^2)$ 意味着 $10^8$ 次运算，逼近多数判题环境的超时临界线，因此 $O(n^2)$ 同样不够稳妥。

题解原文还提到一条替代路线：树状数组。利用树状数组维护值域上的前缀最值/计数，配合值域离散化，可以做到 $O(n \log n)$，能够通过本题。但树状数组方案代码量较大，且需要额外理解离散化等前置知识，并非本题的最优解。真正的亮点在于下面的单调栈 $O(n)$ 做法——它比树状数组更快，代码也更简洁。

三、从 132 的结构特性出发：三种枚举视角

在确定一个数之后，如何快速找到另外两个数？题解从 132 结构中每个位置的"角色"出发，给出了三种分析视角：

1. 枚举i（1 的角色）：i是 132 结构中最小的数，需要从i后面找到一对(j, k)，使得两者都大于i，且 $j > k$。由于遍历是单向的，可以转化为：找k，要求k > i，同时保证在[i, k]之间存在比k更大的数。

2. 枚举j（3 的角色）：j是 132 结构里最大的数，需要在j的右边找比j小的「最大」的数，在j的左边找比j小的「最小」的数。这很容易联想到单调栈，但朴素单调栈只能帮我们找到左边或右边「最近」的数，无法直接满足「最大」和「最小」的要求，需要引入额外逻辑。

3. 枚举k（2 的角色）：k是 132 结构中的中间值，分析逻辑与枚举i类似：遍历是单向的，需要找到k左边的i，同时确保[i, k]之间存在比i和k都大的数字。

三种视角在原理上均可行，但题解明确指出**「枚举i」的做法最简单**，核心原因是一句关键观察：

因为如果存在(j,k)满足要求的话，我们只需要找到一个最大的满足条件的k，通过与i的比较即可。

也就是说：只要把"在i右侧是否存在合法(j,k)"压缩成一个标量k（右侧可供选择的、满足"有更大元素垫背"的最大值），那么对i的判定就退化为一次简单的大小比较。而"右侧是否存在 $j > k$ 的合法对"恰好是单调栈最擅长维护的信息。

四、核心算法：逆序遍历 + 单调递减栈

4.1 前置知识：单调栈能做什么

单调栈是本题的算法底座。在 单调栈专题 中，仓库收录了 42. 接雨水（困难）、496. 下一个更大元素 I（简单）、503. 下一个更大元素 II（中等）、739. 每日温度（中等） 等一系列同类问题。

单调栈的核心能力是：在 $O(n)$ 时间内，为每个元素找到其某一侧"第一个比它大/小"的元素。以 496 题为例（题解原文）：

• 对数组逆序遍历，实时维护一个单调栈；
• 遍历到nums[i]时，先弹出栈顶所有比nums[i]小的元素；
• 若栈空，说明右侧没有更大的元素；否则栈顶即为右侧最近的大于nums[i]的元素。

本题的关键差异在于：我们不仅需要"最近"，更需要把所有被弹出的元素中的最大值保留下来，作为 132 结构中"2"的候选值。

4.2 算法流程

题解的处理过程可以概括为两句话：

我们从后往前遍历，维护一个「单调递减」的栈，同时使用k记录所有出栈元素的最大值（k代表 132 结构中的 2）。当遍历到某个nums[i] < k时，说明找到了符合条件的i j k。

具体流程如下：

1. 初始化一个空栈，k初始化为极小值（代码中使用 $-0x3f3f3f3f$，约等于 $-1.06 \times 10^9$，小于题目给定的数值下界 $-10^9$，确保第一次比较不会被误触发）；
2. 从右向左遍历nums：
   • 若nums[i] < k，直接返回true（找到了 1）；
   • 否则，将栈中所有小于nums[i]的元素依次弹出，并用k记录弹出元素中的最大值（这些被弹出的元素及其"垫背"关系正是合法的 32 结构）；
   • 将nums[i]入栈；
3. 若遍历结束仍未返回，说明不存在 132 模式，返回false。

4.3 过程演示：以[3, 1, 4, 2]为例

已知该样例的答案是[1, 4, 2]，即 $i$ 取1、$j$ 取4、$k$ 取2。我们从后往前模拟：

1. 枚举到 2：栈内元素为[2]，k = INF（初始极小值），不满足nums[i] < k；
2. 枚举到 4：4 > 2，不满足单调递减，弹出2并更新k = 2，随后4入栈。此时栈内为[4]，k = 2。注意：4入栈后，栈仍保持单调递减（4在栈底，2已出栈）；
3. 枚举到 1：满足nums[i] = 1 < k = 2，返回true。

为什么第 3 步的判定是成立的？因为：

• 1 < 2满足了i与k之间的大小关系（132 中的1 < 2）；
• 而k = 2之所以有值，是因为它曾作为4的"牺牲品"被弹出——这意味着4 > 2，即j > k（132 中的3 > 2）确实存在，且4的位置在1与2之间（因为4比1更靠左、比2更靠右才可能在逆序扫描中形成这一弹出关系）。

于是 $(1, 4, 2)$ 三个位置恰好构成完整的 132 模式。

4.4 算法的本质

题解对这一做法的本质做了精确概括：

我们通过维护「单调递减」来确保已经找到了有效的(j,k)。换句话说如果k有值的话，那么必然是因为有j > k，导致的有值。也就是 132 结构中，我们找到了 32，剩下的i（也就是 132 结构中的 1）则是通过遍历过程中与k的比较来找到。

一句话总结：单调栈负责在 $O(n)$ 内"发现并记录"所有可能的 32 组合中的最优k，剩余的一维枚举交给单次逆序扫描完成，两相结合把原本的三重枚举压成了单趟遍历。

五、正确性证明

从过程上看算法自洽，题解进一步给出了严谨的证明。

设数组中真实存在满足 132 结构的三元组，我们取所有合法组合中k最大的那一组记为ijk。由于算法对i的遍历是从后往前的，i必然会被遍历到；因此若算法漏掉了这组ijk，只可能是：在遍历到i的时刻，变量k没有被更新到真实组合中的k值。此时分两种情况讨论：

1. 变量k小于真实值：说明真正的k此时还在栈中未被弹出，而遍历位置已经到达了i，这意味着j与k同时存在于栈中。但栈是单调递减的——栈内元素自底向上严格递减，k < j时二者不可能同栈，与单调性矛盾。

2. 变量k大于真实值：说明在真正的k出栈之后，又有比k更大的数值出栈并刷新了变量（同时必然有比该变量更大的值仍在栈中垫底）。但这要么与"ijk是所有合法组合中k最大的组合"这一假设冲突（存在更大的k值组合），要么与"当前遍历位置是i"的事实冲突（说明有更大的元素出现在i右侧更远处，结构上不再符合 $i<j<k$ 的相对顺序）。

综合两种情况：

由于「单调递减」的性质，我们至少能找到「遍历过程中」所有符合条件的ijk中k最大的那个组合。

一旦找到该组合，遍历到它的i时nums[i] < k判定必然成立，算法必返回true；若全数组不存在 132 模式，则全程无元素能刷新k且所有nums[i] \ge k，最终返回false。正确性得证。

六、代码实现（四种语言）

以下代码直接取自 456. 132 模式（中等） 题解原文，可在 LeetCode 456 题直接提交运行。

Java

class Solution { public boolean find132pattern(int[] nums) { Deque<Integer> d = new ArrayDeque<>(); int n = nums.length, k = -0x3f3f3f3f; for (int i = n - 1; i >= 0; i--) { if (nums[i] < k) return true; while (!d.isEmpty() && d.peekLast() < nums[i]) { // 事实上，k 的变化也具有单调性，直接使用 k = pollLast() 也是可以的 k = Math.max(k, d.pollLast()); } d.addLast(nums[i]); } return false; } }

C++

class Solution { public: bool find132pattern(vector<int>& nums) { stack<int> st; int n = nums.size(), k = -0x3f3f3f3f; for(int i = n - 1; i >= 0; i--){ if(nums[i] < k) return true; while(!st.empty() and st.top() < nums[i]) { k = max(k, st.top()); st.pop(); } st.push(nums[i]); } return false; } };

Python3

class Solution: def find132pattern(self, nums: List[int]) -> bool: stack = [] n, k = len(nums), -0x3f3f3f3f for i in range(n - 1, -1, -1): if nums[i] < k: return True while stack and stack[-1] < nums[i]: k = max(k, stack.pop()) stack.append(nums[i]) return False

TypeScript

function find132pattern(nums: number[]): boolean { const d = []; let n = nums.length, k = -0x3f3f3f3f; for (let i = n - 1; i >= 0; i--) { if (nums[i] < k) return true; while (d.length > 0 && d[d.length - 1] < nums[i]) { k = Math.max(k, d.pop()!); } d.push(nums[i]); } return false; };

实现要点说明

• k的初始值：$-0x3f3f3f3f$（约 $-1.06 \times 10^9$），严格小于题目下界 $-10^9$，保证初始状态下nums[i] < k永不成立，不会误判；
• 栈的单调性：每次弹出所有比nums[i]小的栈顶元素后入栈，保证栈自底向上严格递减；
• k的更新：k取所有出栈元素的最大值。题解注释特别指出，k的变化本身也具有单调性（每次出栈元素必然大于之前记录的k），因此直接写k = pollLast()同样正确；使用Math.max只是形式上更严谨、更易读；
• 提前返回：一旦发现nums[i] < k，立即返回true，无需继续扫描。

复杂度分析

• 时间复杂度：$O(n)$。每个元素最多入栈一次、出栈一次，均摊 $O(1)$；
• 空间复杂度：$O(n)$。最坏情况下（如数组单调递减）栈中需要容纳全部 $n$ 个元素。

该复杂度优于进阶要求中的 $O(n \log n)$ 树状数组方案，也远优于 $O(n^2)$ 的枚举优化方案。

七、边界情况与易错点

• 数组含负数：k的初始值必须小于全部元素（含负数），$-0x3f3f3f3f$ 即为本题下界的合适选择；若误用Integer.MIN_VALUE或-1之类的值，可能在负数场景下漏判；
• 长度不足 3：$n < 3$ 时不可能存在三元组，算法自然返回false，无需特判；
• 严格不等号：132 模式要求严格小于/大于，因此代码中统一使用</>比较，等于的情况（如nums[i] == k）不能触发命中；
• k是"右侧"信息：务必注意逆序遍历的方向性——k记录的一定是当前i右侧（已扫描过的区域）被弹出的最大值，这保证了 $i < j < k$ 的下标顺序约束。

八、同类问题与延伸阅读

本题是"单调栈"思想的经典应用场景之一，仓库的 单调栈专题 汇总了完整的同类题目清单，推荐配合研读：

• 42. 接雨水（困难）：单调栈经典应用，利用栈维护柱子的高度关系；
• 496. 下一个更大元素 I（简单）：逆序遍历 + 单调栈找右侧最近更大元素，是理解 132 模式算法的基础模板；
• 84. 柱状图中最大的矩形（困难）：单调栈 + 边界扩展的进阶应用；
• 739. 每日温度（中等）：单调栈的入门级实操题。

研读建议：先通过 496 题掌握"逆序遍历 + 单调栈维护右侧信息"的基本盘，再回到本题体会"单调栈 + 出栈元素最值"如何把两维约束压缩成一维比较——这种"用栈维护局部结构、用标量记录全局最优候选"的组合技巧，在区间类、子序列类问题中具有很高的复用价值。

本系列完整题解按题目编号组织于仓库LeetCode/目录下（如本文对应 LeetCode/451-460/456. 132 模式（中等）.md），按算法分类的索引见Index/目录，可继续翻阅对应专题深化学习。

• 教程
• 文档