Python|单调栈判断132模式

简介: Python|单调栈判断132模式

问题描述

给定一个整数序列:a1, a2, ..., an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak < aj。设计一个算法,当给定有 n 个数字的序列时,验证这个序列中是否含有132模式的子序列。

示例1:

输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。

示例 2:

输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列:[1, 4, 2].


解决方案

简单来说,就是在所给序列中,有没有某一个长度为3的子序列符合中间大于两边,右边大于左边。

也就是说,找到一个元素A, 在它左边有比它小的元素B,在它右边也有比它小的元素C, 并且B要小于C。

但暴力法容易超时。这里可以利用单调减栈,倒着遍历数组,当数组某个元素大于单调减栈的最大值时,这个元素就相当于A,单调减栈的最大值相当于C,而且这个C是A右边区域的最大值,更容易找到比它小的元素,接着遍历,如果出现比元素C还小的值,就找到了元素A,返回True

代码示例:

class Solution:

    def find132pattern(self, nums: List[int]) -> bool:

        stack = []

        # 设置m的初始值为负无穷

        m = float('-inf')

        for i in range(len(nums)-1, -1, -1):

            if nums[i] < m:

                return True

            while stack and nums[i] > stack[-1]:

                m = stack.pop()

            stack.append(nums[i])

        return False


结语

这道题给人的感觉很简单,但直接使用暴力法找所需的三个数很容易超时。这里利用的是单调减栈,这样理论上在遍历过程中可以同时找到最大的元素和右边次大的元素,如果找到了,那么接着遍历找到比右边次大的元素要小的元素是比较容易的。



目录
相关文章
|
4天前
|
Python
Python实现数据结构(如:链表、栈、队列等)。
Python实现数据结构(如:链表、栈、队列等)。
259 0
|
4天前
|
前端开发 Python
Python中如何用栈实现队列
Python中如何用栈实现队列
214 0
|
4天前
|
存储 Python
Python中栈的概念和使用
Python中栈的概念和使用
35 0
|
4天前
|
自然语言处理 算法 数据挖掘
Python怎么实现模式匹配
Python怎么实现模式匹配
20 0
|
4天前
|
存储 Python
如何在Python中读取文件的权限模式?
【2月更文挑战第15天】【2月更文挑战第44篇】如何在Python中读取文件的权限模式?
|
4天前
|
Python
在Python中,如何指定文件的读取和写入模式?
【2月更文挑战第10天】【2月更文挑战第27篇】在Python中,如何指定文件的读取和写入模式?
|
8月前
|
设计模式 Python
Python 生成器模式讲解和代码示例
Python 生成器模式讲解和代码示例
53 0
|
4天前
|
C++ Python Java
Python每日一练(20230424) 滑动窗口最大值、栈实现队列、直线上最多的点数
Python每日一练(20230424) 滑动窗口最大值、栈实现队列、直线上最多的点数
548 0
Python每日一练(20230424) 滑动窗口最大值、栈实现队列、直线上最多的点数
|
4天前
|
Go Python 算法
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
743 0
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
|
4天前
|
存储 Shell 程序员
Python 自动化指南(繁琐工作自动化)第二版:七、使用正则表达式的模式匹配
Python 自动化指南(繁琐工作自动化)第二版:七、使用正则表达式的模式匹配
65 0