Skip to content

Latest commit

 

History

History
112 lines (67 loc) · 4.27 KB

456.132-pattern.md

File metadata and controls

112 lines (67 loc) · 4.27 KB

题目地址(456. 132 模式)

https://leetcode-cn.com/problems/132-pattern/

题目描述

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

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

 

进阶:很容易想到时间复杂度为 O(n^2) 的解决方案,你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗?

 

示例 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 <= 104
-109 <= nums[i] <= 109

前置知识

公司

  • 暂无

思路

132 模式指的是满足:大小关系是 1 < 2 < 3 ,索引关系是 1 < 3 < 2 的三个数。

一个简单的思路是使用一层从左到右的循环固定 3,遍历的同时维护最小值,这个最小值就是 1(如果固定的 3 不等于 1 的话)。 接下来使用另外一个嵌套寻找枚举符合条件的 2 即可。 这里的符合条件指的是大于 1 且小于 3。这种做法的时间复杂度为 $O(n^2)$,并不是一个好的做法,我们需要对其进行优化。

实际上,我们也可以枚举 2 的位置,这样目标变为找到一个大于 2 的数和一个小于 2 的数。由于 2 在序列的右侧,因此我们需要从右往左进行遍历。又由于题目只需要找到一个 132 模式,因此我们应该贪心地选择尽可能大的 2(只要不大于 3 即可),这样才更容易找到 1(换句话说不会错过 1)。

首先考虑找到 32 模式。我们可以使用从右往左遍历的方式,当遇到一个比后一位大的数时,我们就找到了一个可行的 32 模式。

和上面思路类似,维护一个全局最小值即可,这样就不会错过答案。可是这样就无法做到前面提到的贪心地选择尽可能大的 2,我们选择的 2 实际上是尽可能小的 2。那如何找到尽可能大的并且比当前数(3)小的 2 呢?

其实,我们可以维护一个递增栈。每次遇到一个比栈顶大的数就 pop 栈,直到栈顶比当前数字还大。那么最后一次 pop 出去的就是满足条件的最大的 2 了。找到了 32 模式,接下来,我们只需要找到一个比 2 小的数就可以直接返回 True 了。

关键点

  • 先找到 32 模式,再找 132 模式。
  • 固定 2, 从右往左遍历,使用单调栈获取最大的小于当前数的 2,并将当前数作为 3 。

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def find132pattern(self, A: List[int]) -> bool:
        stack = []
        p2 = float("-inf")
        for a in A[::-1]:
            # p2 不为初始值意味着我们已经找到了 32 模式,因此 a < p2 时候,我们就找到了 132 模式
            if a < p2:
                return True
            while stack and a > stack[-1]:
                p2 = stack.pop()
            stack.append(a)

        return False

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。