456. 132 模式

🎯 问题描述

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

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

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

说明：

这是一个枚举中间最大值结合有序集合维护后缀的问题。
核心策略：
- 我们要找 $nums[i] < nums[k] < nums[j]$ 。
- 我们可以枚举中间的元素 nums[j] 作为“3”（最大值）。
- 左侧 (1)：为了让 $nums[i] < nums[k]$ 更容易满足，对于固定的 j，我们需要知道 j 左侧的最小值 min_left。
- 右侧 (2)：我们需要在 j 的右侧找到一个数 nums[k]，使得 min_left < nums[k] < nums[j]。
数据结构：
- 左侧最小值可以通过变量动态维护。
- 右侧的数可以使用一个有序列表来维护，利用二分查找快速找到大于 min_left 的最小值。
示例：
示例 1：

输入：nums = [3, 1, 4, 2]
输出：true
解释：
- 序列中有 132 模式：[-1, 4, 2] (对应下标 1, 2, 3)。
- j=2 (nums[j]=4)。
- 左侧最小值 pre = min(3, 1) = 1。
- 右侧集合 suf = [2]。
- 我们需要在 suf 中找 > 1 且 < 4 的数。
- 找到 2，满足条件，返回 True。

💻 解题思路

思路1：枚举中间点 + 有序后缀集合

核心逻辑

初始化：
- pre：记录 nums[0...j-1] 的最小值，初始为 nums[0]。
- suf：一个有序列表，初始包含 nums[2...n-1] 的所有元素。这是因为 j 从 1 开始，右侧至少要有 k。
枚举中间点 j：
- 遍历 j 从 1 到 n-2。
- 查找目标 k：
  - 我们需要在 suf 中找到一个数 nums[k]，满足 pre < nums[k] < nums[j]。
  - 利用二分查找 bisect_right(suf, pre) 找到第一个严格大于 pre 的元素的位置 idx。
  - 如果 idx 合法（即存在这样的元素），检查该元素 suf[idx] 是否小于 nums[j]。
  - 如果满足 suf[idx] < nums[j]，说明找到了 132 模式，返回 True。
- 更新状态：
  - 更新左侧最小值：pre = min(pre, nums[j])。
  - 更新右侧集合：将即将成为下一个 j 的当前 nums[j+1] 从 suf 中移除（因为下一轮循环中，j 会右移，原来的 j+1 变成了中间的 j，不再是右侧的 k）。

代码实现

import bisect

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
            
        # 1. 初始化左侧最小值
        pre = nums[0]
        
        # 2. 初始化右侧有序集合
        # 初始包含 nums[2] 到 nums[n-1]
        suf = []
        for i in range(2, n):
            bisect.insort(suf, nums[i])
            
        # 3. 枚举中间点 j (从 1 到 n-2)
        for j in range(1, n - 1):
            # 4. 在右侧集合中查找 > pre 的最小数
            # bisect_right 返回第一个 > pre 的元素的索引
            idx = bisect.bisect_right(suf, pre)
            
            # 5. 检查是否存在这样的数，且该数 < nums[j]
            if idx < len(suf) and suf[idx] < nums[j]:
                return True
            
            # 6. 更新左侧最小值
            pre = min(pre, nums[j])
            
            # 7. 更新右侧集合：移除 nums[j+1]
            # 因为下一轮 j 会变成 j+1，所以 nums[j+1] 不再是右侧元素
            if j + 1 < n:
                del_idx = bisect.bisect_left(suf, nums[j+1])
                # 确保元素存在再删除
                if del_idx < len(suf) and suf[del_idx] == nums[j+1]:
                    suf.pop(del_idx)
                    
        return False

📊 性能分析

时间复杂度： $O(N^2)$ $O (N^{2})$
- 外层循环遍历 j，共 $N$ 次。
- 内层操作中，bisect.insort（初始构建）和 suf.pop（删除元素）在 Python 的列表中都是 $O(N)$ 的操作（因为需要移动元素）。
- 二分查找是 $O(\log N)$ 。
- 总时间复杂度为 $O(N^2)$ 。
空间复杂度： $O(N)$ $O (N)$
- 列表 suf 最多存储 $N$ 个元素。

思考

为什么使用 bisect_right？
- 题目要求 nums[i] < nums[k]（严格小于）。
- bisect_right(suf, pre) 返回的是第一个大于 pre 的元素的位置。
- 如果使用 bisect_left，当 suf 中存在等于 pre 的元素时，会返回该元素的索引，导致 nums[k] == nums[i]，不满足条件。
贪心策略：
- 在右侧寻找 nums[k] 时，我们只需要找到任意一个满足 pre < nums[k] < nums[j] 的数即可。
- 通过 bisect_right 找到的 suf[idx] 是右侧大于 pre 的最小数。
- 如果这个最小的候选数都小于 nums[j]，那么一定存在解。
- 如果这个数大于等于 nums[j]，那么右侧其他更大的数肯定也大于等于 nums[j]，无法满足 nums[k] < nums[j]。
左侧最小值的维护：
- pre 始终代表 nums[0...j-1] 的最小值。
- 这是为了让 nums[i] 尽可能小，从而让 nums[k] 的选择范围（nums[k] > nums[i]）尽可能大。
右侧集合的更新：
- 随着 j 向右移动，原本属于“右侧”的 nums[j+1] 变成了“中间”的 nums[j]。
- 因此，必须在每轮循环结束时将其从 suf 中移除。