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


结语

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



目录
相关文章
|
5月前
|
前端开发 Python
Python中如何用栈实现队列
Python中如何用栈实现队列
232 0
|
7天前
|
算法 数据挖掘 Python
Python中的拟合技术:揭示数据背后的模式
Python中的拟合技术:揭示数据背后的模式
18 0
Python中的拟合技术:揭示数据背后的模式
|
11天前
|
IDE JavaScript Java
Processing介绍及几个python模式下的案例
该文章介绍了Processing这一开源编程语言和环境,主要用于视觉艺术和设计领域,并提供了Python模式下的编程案例。
27 5
|
16天前
|
设计模式 安全 API
探索Python中的异步编程模式
【9月更文挑战第19天】在本文中,我们将深入探讨Python的异步编程世界。通过理解其背后的原理和实践应用,你将学会如何编写更加高效、响应更快的程序。文章将引导你从基础概念出发,逐步过渡到高级用法,确保你能够自信地运用异步特性来优化你的代码。
|
27天前
|
Python Windows
Python交互模式
Python交互模式。
11 1
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
20 4
|
2月前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案,通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
22 6
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
使用两个栈实现队列的Python解决方案,包括初始化两个栈、实现在队列尾部添加整数的appendTail方法和在队列头部删除整数的deleteHead方法,以及相应的示例操作。
36 2
|
2月前
|
存储 中间件 PHP
Python编程入门:从零到一的代码实践深入理解 PHP 中的中间件模式
【8月更文挑战第28天】本文旨在通过浅显易懂的方式,向初学者介绍Python编程的基础知识,并结合具体代码示例,带领读者一步步实现从零基础到能够独立编写简单程序的转变。文章将围绕Python语言的核心概念进行讲解,并通过实例展示如何应用这些概念解决实际问题。无论你是编程新手还是希望扩展技能的专业人士,这篇文章都将为你打开编程世界的大门。 【8月更文挑战第28天】在PHP的世界中,设计模式是构建可维护和可扩展软件的重要工具。本文将通过浅显易懂的语言和生动的比喻,带领读者深入理解中间件模式如何在PHP应用中发挥魔力,实现请求处理的高效管理。我们将一步步揭开中间件的神秘面纱,从它的定义、工作原理到
|
3月前
|
网络协议 Python
python对tcp协议栈进行优化之一
**TCP优化摘要:** - MSS优化涉及调整TCP最大段大小,Python中可使用`socket.getsockopt()`查询MSS。 - Scapy是Python库,用于创建和发送网络包,可用于测试和优化协议栈性能。 - LwIP是轻量级TCP/IP协议栈,适合嵌入式设备,可通过分析和调整提升性能,特别是实时性和资源管理。
下一篇
无影云桌面