132 模式

2024-04-09 09:48
文章标签 模式 132

本文主要是介绍132 模式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

456. 132 模式

给你一个整数数组 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 模式的子序列。

来源:力扣(LeetCode)

看见这题的时候我就猜到应该能用单调栈,但就是写不出来,难受,过了半个月,回头来写还是写不出,无奈之中只能看题解了,再大佬题解的帮助下,总算是搞懂了

思路:不找132,而是反向遍历找231
要找132的话,找的是2,因此既要满足>1,又要满足<3
而找231的话,找的是1,因此只要小于2即可

那么怎么利用单调栈找到23呢?很明显23递增,那么我们维护一个递减栈(从顶到底递减),当栈里一直是递减的时候,就不可能会出现23,因为23是递增,但是一旦有一个数破坏了栈的单调性,那么就该干活了,因为此时已经有了若干对23了,3是破坏单调的(即当前遍历到)的元素,而此时栈内的所有小于3的元素都能当作2,我们要找的是小于2的数,那么再若干个2里,我们必须取最大的一个,这样才能保证覆盖所有情况

然后为了不影响站的单调性,我们一边弹出栈顶一边取最大的2值

这里注意一下,因为我们这种找2的方法,所以每一个2都一定是有效的,因为前面一定有比它还大的3存在

然后就差一步判断当前元素是否小于最大的2了,这一步必须放在最开始,不然的话,最大2可能因为当前元素更新,这时再判断,就晚了

class Solution {
public:bool find132pattern(vector<int>& nums) {stack<int>st;int val = INT_MIN;//储存最大2for(int i = nums.size()-1;i>=0;--i){//反向遍历找231if(nums[i]<val)return true;//因为初始化为INT_MIN,所以不会有问题while(!st.empty() && nums[i]>st.top()){//维护单调性val = max(val,st.top());st.pop();//取最大2}st.push(nums[i]);//将当前数字存入栈}return false;}
};

这篇关于132 模式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/887822

相关文章

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

大数据spark3.5安装部署之local模式详解

《大数据spark3.5安装部署之local模式详解》本文介绍了如何在本地模式下安装和配置Spark,并展示了如何使用SparkShell进行基本的数据处理操作,同时,还介绍了如何通过Spark-su... 目录下载上传解压配置jdk解压配置环境变量启动查看交互操作命令行提交应用spark,一个数据处理框架

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例

在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲

1. 单例模式(Singleton Pattern) 确保一个类只有一个实例,并提供一个全局访问点。 示例代码: class Singleton {constructor() {if (Singleton.instance) {return Singleton.instance;}Singleton.instance = this;this.data = [];}addData(value)

模版方法模式template method

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/template-method 超类中定义了一个算法的框架, 允许子类在不修改结构的情况下重写算法的特定步骤。 上层接口有默认实现的方法和子类需要自己实现的方法

【iOS】MVC模式

MVC模式 MVC模式MVC模式demo MVC模式 MVC模式全称为model(模型)view(视图)controller(控制器),他分为三个不同的层分别负责不同的职责。 View:该层用于存放视图,该层中我们可以对页面及控件进行布局。Model:模型一般都拥有很好的可复用性,在该层中,我们可以统一管理一些数据。Controlller:该层充当一个CPU的功能,即该应用程序

迭代器模式iterator

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/iterator 不暴露集合底层表现形式 (列表、 栈和树等) 的情况下遍历集合中所有的元素

《x86汇编语言:从实模式到保护模式》视频来了

《x86汇编语言:从实模式到保护模式》视频来了 很多朋友留言,说我的专栏《x86汇编语言:从实模式到保护模式》写得很详细,还有的朋友希望我能写得更细,最好是覆盖全书的所有章节。 毕竟我不是作者,只有作者的解读才是最权威的。 当初我学习这本书的时候,只能靠自己摸索,网上搜不到什么好资源。 如果你正在学这本书或者汇编语言,那你有福气了。 本书作者李忠老师,以此书为蓝本,录制了全套视频。 试