DeepSeek LeetCode 456. 132 模式 Java实现

LeetCode 456. 132 模式

题目思路

判断是否存在下标 i < j < k，满足 nums[i] < nums[k] < nums[j]。

核心思想：从右往左遍历 + 单调栈

· 从右往左扫描，把当前元素看作 “1”（最小值）
· 用单调递减栈维护可能的 “3”（较大值）
· 用变量 second 记录已确定的 “2” 的最大值（即被弹出的栈元素）
· 当 nums[i] < second 时，说明存在 nums[i] < nums[k] < nums[j]，返回 true

关键点：栈中被弹出的元素，代表它左边有更大的数（“3”），因此它可以作为 “2”；我们总是保留其中最大的那个作为 second，这样更容易让左边的数成为 “1”。

Java 代码

classSolution{publicbooleanfind132pattern(int[]nums){intn=nums.length;if(n<3)returnfalse;Deque<Integer>stack=newArrayDeque<>();// 单调递减栈（栈顶最小）intsecond=Integer.MIN_VALUE;// "2" 的最大候选值for(inti=n-1;i>=0;i--){// 当前的 nums[i] 作为 "1"，只要小于 second 就成立if(nums[i]<second){returntrue;}// 维护单调递减栈；被弹出的元素可以成为 "2"while(!stack.isEmpty()&&nums[i]>stack.peek()){second=Math.max(second,stack.pop());}stack.push(nums[i]);}returnfalse;}}

复杂度分析

· 时间复杂度：O(n)，每个元素最多进栈、出栈一次
· 空间复杂度：O(n)，栈的最大容量

示例验证

以 nums = [3, 1, 4, 2] 为例（答案应为 true，1 < 2 < 4）：

i nums[i] stack（栈底→栈顶） second 说明
3 2 [2] MIN 入栈
2 4 [4] 2 弹出 2，second=2；4 入栈
1 1 [4, 1] 2 1 < 2，但 1 不能作为 “1”（因为它右边没有比 2 小的"3"已成立？）——1 < second 成立，返回 true

等等——这里其实是 nums[1]=1 < second=2，直接返回 true。验证：i=1, j=2, k=3，1 < 2 < 4 ✓。

其他可行解法（对比）

解法 时间 空间 说明
单调栈（上述） O(n) O(n) 最优解，面试推荐
TreeMap 从右扫描 O(n log n) O(n) 维护右侧已访问元素中 > nums[i] 的最小值
暴力三层循环 O(n³) O(1) 仅用于理解题意
预处理 min + 双层循环 O(n²) O(n) 左最小值数组 + 右侧扫描