What is the 132 pattern in an array?

A 132 pattern is a subsequence of three integers nums[i], nums[j], nums[k] where i < j < k and nums[i] < nums[k] < nums[j].

Can duplicates exist in the 132 pattern detection?

Yes, duplicates can exist elsewhere in the array, but the relative order of the subsequence must satisfy nums[i] < nums[k] < nums[j].

What is an efficient way to detect a 132 pattern?

Use a monotonic stack while traversing the array from the end and track the minimum element for '1' to detect the pattern in O(n) time.

Why is a monotonic stack used in this problem?

It efficiently tracks potential '3' values while allowing fast comparison against the '2' candidate without checking all previous elements.

Can binary search optimize finding the '2' in the 132 pattern?

Yes, using an ordered set or sorted structure allows binary search to find a valid '2' candidate between the minimum '1' and current '3', reducing unnecessary checks.

#456

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

132 模式

给你一个整数数组 nums ，数组中共有 n 个整数。 132 模式的子序列由三个整数 nums[i] 、 nums[j] 和 nums[k] 组成，并同时满足： i 和 nums[i] 。如果 nums 中存在 132 模式的子序列，返回 true ；否则，返回 false 。示例 1： …

数组二分查找栈单调栈有序集合

题目描述

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

示例 3：

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

提示：

n == nums.length
1 <= n <= 2 * 10⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：单调栈

我们可以枚举从右往左枚举整数 $nums[i]$ ，并维护一个单调栈，栈中的元素从栈底到栈顶单调递减。维护一个变量 $vk$ ，表示 $nums[i]$ 右侧且小于 $nums[i]$ 的最大值。初始时， $vk$ 的值为 $-\infty$ 。

我们从右往左遍历数组，对于遍历到的每个元素 $nums[i]$ ，如果 $nums[i]$ 小于 $vk$ ，则说明我们找到了一个满足 $nums[i] \lt nums[k] \lt nums[j]$ 的三元组，返回 true。否则，如果栈顶元素小于 $nums[i]$ ，则我们循环将栈顶元素出栈，并且更新 $vk$ 的值为出栈元素，直到栈为空或者栈顶元素大于等于 $nums[i]$ 。最后，我们将 $nums[i]$ 入栈。

如果遍历结束后仍未找到满足条件的三元组，说明不存在这样的三元组，返回 false。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        vk = -inf
        stk = []
        for x in nums[::-1]:
            if x < vk:
                return True
            while stk and stk[-1] < x:
                vk = stk.pop()
            stk.append(x)
        return False

speed

复杂度分析

指标	值
时间	complexity is O(n) using a single pass with a monotonic stack or O(n log n) when binary searching over a sorted set of '2' candidates. Space complexity is O(n) for storing the stack or ordered set for candidate tracking.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate considers tracking min values for '1' positions and stack management for '3'.
question_mark
Candidate attempts O(n^2) brute force and may need guidance toward monotonic stack or binary search over valid answers.
question_mark
Candidate mentions handling negative numbers and duplicate elements carefully to avoid false negatives.

warning

常见陷阱

外企场景

error
Assuming the 132 pattern elements must be consecutive rather than a subsequence.
error
Failing to update or correctly maintain the stack or min value, causing missed patterns.
error
Overcomplicating with unnecessary nested loops instead of using a single-pass stack approach.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Detect 321 or 213 patterns instead, adjusting stack logic accordingly.
arrow_right_alt
Return all indices of valid 132 patterns instead of just true/false.
arrow_right_alt
Handle streaming input where the array is too large to store entirely in memory.

help

常见问题

外企场景

继续练习

#975 奇偶跳 #493 翻转对 #496 下一个更大元素 I