0456：132 模式（★）

2016-03-31 约 522 字预计阅读 2 分钟次阅读

力扣第 456 题

题目

给你一个整数数组 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⁹

分析

#1

考虑遍历中间的 nums[j]

往 j 左侧找到最小的数 nums[i]，然后在 j 右侧找介于两者之间的数 nums[k] 即可
左侧最小值在遍历中即可维护
右侧需要维护一个有序集合，然后二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        from sortedcontainers import SortedList
        a, sl = inf, SortedList(nums)
        for b in nums:
            sl.remove(b)
            if a<b:
                pos = sl.bisect_right(a)
                if pos<len(sl) and sl[pos]<b:
                    return True
            a = min(a, b)
        return False

565 ms

#2

还可以考虑遍历右边的 nums[k]：

往 k 左侧找到第一个更大的数 nums[j]，然后在 j 左侧找最小的数 nums[i] 即可
前缀最小值可以在遍历时维护
找上一个最大元素即是典型的单调栈问题

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

189 ms

目录

0456：132 模式（★）

题目

分析

#1

#2

解答