LeetCode 456. 132 模式
题目描述
题意分析
寻找
i < j < k且nums[i] < nums[k] < nums[j]的三个元素。它们不要求连续，“1、3、2”表示三个值从小到大的相对排名，并不是数值本身。如果右侧已经有一对下标递增、数值递减的“3、2”，只需在它们左侧找到比“2”更小的“1”。因此从右向左扫描，先维护右侧已经配好的“3、2”，再判断当前值能否补全模式。
解法：从右向左维护单调栈
核心思路
[!blue]
middle保存已经确认的“2”候选中的最大值：它在右侧出现过，并且在它左边、当前扫描位置右边，已经出现过一个更大的“3”。若当前nums[i] < middle，这三个数既满足数值关系，也天然满足i < j < k，可以立即返回true。在已经配好“3”的候选中，“2”越大，越容易在左侧找到比它小的值，所以只保留最大者即可。另用栈保存右侧尚未被弹出的值，栈从底到顶非递增。当前值
x大于栈顶时，将栈顶弹出：x位于弹出值的左边且更大，因此x可以当“3”，弹出值可以当“2”。持续弹出所有小于x的栈顶，弹出值从小到大排列，最后一个就是本轮最优的“2”；随后把x入栈，恢复非递增顺序。代码直接用弹出值覆盖
middle，不会丢失更大的旧候选。原因是：尚未返回时，栈内所有值都不小于已有的middle；当前值也已通过x < middle的检查。新弹出的值因而不会小于旧middle，剩余栈值以及新入栈的x又都不小于新的middle，这个性质会一直保持。也不会漏掉合法模式。对任意合法的
i < j < k，处理j时，若nums[k]仍在栈内，它及其上方更小或相等的元素都会被nums[j]弹出，使middle至少达到nums[k]；若它已经出栈，则此前已经确认过不小于它的候选。middle之后不会变小，所以扫描到i时必然能发现模式，或早已发现另一个模式。
解题步骤
- 初始化空栈和尚未设置的
middle，从数组末尾向左扫描。- 若
middle已存在且nums[i] < middle，当前元素可作为“1”，返回true。- 当
nums[i] > stack.top时持续弹栈，把弹出值记为新的middle；当前元素与它构成“3、2”。- 将
nums[i]入栈，继续向左。- 扫描结束仍未命中则返回
false。Java 用
Integer.MIN_VALUE表示尚无候选，它小于题目允许的所有元素；Go 用hasMiddle区分候选是否有效，避免默认值0干扰负数。少于三个元素时不可能完成两次角色确认，循环自然返回false。
代码实现
class Solution {
public boolean find132pattern(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
int middle = Integer.MIN_VALUE;
for (int i = nums.length - 1; i >= 0; i--) {
// 此前已存在右侧的大、中组合，当前更小值可补成一三二。
if (nums[i] < middle) {
return true;
}
while (!stack.isEmpty() && nums[i] > stack.peek()) {
// 当前值作为三，弹出值作为二，继续弹出以获得更有利的二。
middle = stack.pop();
}
stack.push(nums[i]);
}
return false;
}
}
func find132pattern(nums []int) bool {
stack := make([]int, 0)
middle := 0
hasMiddle := false
for i := len(nums) - 1; i >= 0; i-- {
// 此前已存在右侧的大、中组合，当前更小值可补成一三二。
if hasMiddle && nums[i] < middle {
return true
}
for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
// 当前值作为三，弹出值作为二，继续弹出以获得更有利的二。
middle = stack[len(stack)-1]
hasMiddle = true
stack = stack[:len(stack)-1]
}
stack = append(stack, nums[i])
}
return false
}
复杂度分析
- 时间复杂度：$O(n)$。每个元素至多入栈一次、出栈一次，内层循环总弹栈次数不超过 $n$。
- 空间复杂度：$O(n)$。例如原数组从左到右非递减时，逆序扫描不会弹栈，栈可能保存全部元素。
关键点总结
[!green]
- 先让当前值尝试充当“1”，再让它为更左侧的元素建立“3、2”候选。
middle不是任意后缀元素，而是已经有左侧更大值与之配对的“2”。- 单调栈负责发现候选，
middle负责保留最有利的候选，两者作用不同。
易错点总结
[!yellow]
- 改为从左向右套同样逻辑，无法保证“2”位于“3”之后。
middle用 0 初始化且不区分是否有效，会在全负数数组中误报。- 弹栈条件和命中判断都要严格比较；相等的两个值不能承担模式中的不同排名。
- 只弹一次而不用
while，栈可能失去单调性并错过更大的“2”候选。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 503. 下一个更大元素 II | 中等 | 同样用单调栈消除被更优元素覆盖的候选，但本题栈弹出的值还承担132中间项的角色。 |