LeetCode 456. 132 模式

约 5 分钟
文章信息 8 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 虾皮
标签
数组 二分查找 栈 单调栈 有序集合
目录

题目描述

✅ 456. 132 模式

image-20260329111721918

题意分析

要在数组里判断是否存在下标三元组 i < j < k，同时满足 nums[i] < nums[k] < nums[j]。注意这是两个独立要求叠在一起：下标必须严格递增，数值必须是「小、大、中」的形状。返回值只是布尔，不需要给出具体是哪三个位置。

名字里的「132」指的是数值的相对名次而非位置顺序：先出现的 nums[i] 排第 1（最小），中间的 nums[j] 排第 3（最大），最后的 nums[k] 排第 2。三个数必须两两严格不等，nums[i] < nums[k] 和 nums[k] < nums[j] 都不取等号。

约束 n 可到 $2 \times 10^5$，直接三重循环枚举 $O(n^3)$ 必然超时，连 $O(n^2)$ 的双重枚举也很危险，需要接近线性的做法。数值范围含负数（可到 $-10^9$），任何「初始值设 0」的写法都会出错。

边界情况：n < 3 必然返回 false；数组单调递增或单调递减都无解；存在大量重复元素时因为要求严格小于，等值不能配对。

解法：从右向左维护单调栈

核心思路

132 模式要求 i < j < k 且 nums[i] < nums[k] < nums[j]。从右向左扫描时，可以先在已扫描后缀中确定“3”和“2”，再判断当前数能否充当更靠左的“1”。

维护一个从栈底到栈顶单调递减的栈，以及变量 middle：

  • 栈保存右侧尚未与更大左值配对的候选。
  • middle 保存已经确认存在左侧更大值的“2”候选，即某次弹栈得到的值。

当前值大于栈顶时，栈顶位于当前值右侧且更小，于是当前值可作为“3”、弹出值可作为“2”。连续弹出后，最后弹出的值最大，对未来更靠左的“1”最有利。

循环不变量是：处理下标 i 前，若 middle 已设置，则后缀中一定存在下标 j < k，满足 middle = nums[k] < nums[j]；栈保持单调递减。此时只要 nums[i] < middle，三者的下标和数值关系便同时成立，可以立即返回 true。严格比较也会自然排除重复值形成的伪模式。

解题步骤

  1. 初始化空栈和尚未设置的 middle，从数组末尾向左扫描。
  2. 若 middle 已存在且 nums[i] < middle，当前元素可作为“1”，返回 true。
  3. 当 nums[i] > stack.top 时持续弹栈，把弹出值记为新的 middle；当前元素与它构成“3、2”。
  4. 将 nums[i] 入栈，继续向左。
  5. 扫描结束仍未命中则返回 false。

对 [3,1,4,2]，从右侧压入 2；扫描到 4 时弹出 2，得到已经配好的 4 > 2；再扫描到 1 时发现 1 < 2，对应下标 1 < 2 < 3，返回 true。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;

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)$，单调数组下栈可能保存全部元素。

关键点总结

  • 逆序扫描让当前下标天然位于候选“3、2”的左侧。
  • 弹栈意味着找到了 nums[j] > nums[k]，弹出值成为“2”候选。
  • 判断当前值是否小于 middle 必须放在弹栈之前，保证三个位置不同且顺序正确。
  • 弹栈和命中判断都使用严格不等号，等值不能组成 132。
  • 面试时要讲清 middle 的语义，而不是把它误称为普通的右侧最小值。

易错点总结

  • 改为从左向右套同样逻辑，无法保证“2”位于“3”之后。
  • middle 用 0 初始化且不区分是否有效，会在全负数数组中误报。
  • 弹栈条件写成 >=，会允许“3”和“2”相等。
  • 只弹一次而不用 while，栈可能失去单调性并错过更大的“2”候选。
  • 先弹栈再判断当前值，可能把同一位置同时用于“1”和“3”。

相似题目

题目 难度 考察点
496. 下一个更大元素 I 简单 单调栈求右侧第一个更大值
503. 下一个更大元素 II 中等 环形数组上的单调栈
739. 每日温度 中等 单调栈求等待距离
84. 柱状图中最大的矩形 困难 单调栈求左右第一个更小边界
42. 接雨水 困难 单调栈按层结算凹槽