当前位置: 首页 > news >正文

leetcode456 132 Pattern

给定数组,找到 i < j < k i < j < k i<j<k,使得 n u m s [ i ] < n u m s [ k ] < n u m s [ j ] nums[i] < nums[k] < nums[j] nums[i]<nums[k]<nums[j]

最开始肯定想着三重循环,时间复杂度 O ( n 3 ) O(n^3) O(n3)
接着是二重循环
先找到一组 i < j i <j i<j,使得 n u m s [ i ] < n u m s [ j ] nums[i] < nums[j] nums[i]<nums[j],接着在后面找能放在中间的 k k k
其中 n u m s [ i ] nums[i] nums[i]只要存储左边最小,因为他比其他的更有潜力成为答案

class Solution {
public:bool find132pattern(vector<int>& nums) {int n = nums.size();if(n < 3)return false;bool flag = true;int min_i = nums[0];for(int j = 1; j + 1 < n; ++j){if(nums[j] < min_i){min_i = nums[j];continue;}for(int k = j + 1; k < n; ++k){if(min_i < nums[k] && nums[k] < nums[j]){return true;}}}return false;}
};

然后发现还是超时

所以要一个循环

考虑从右往左遍历
维护一个单调递减栈
当前元素大于栈顶元素时出栈,出栈的最后一个元素作为 n u m s [ k ] nums[k] nums[k]
这样的话相当于先找到了 n u m s [ k ] < n u m s [ j ] nums[k] < nums[j] nums[k]<nums[j]
之后只要找 n u m s [ i ] nums[i] nums[i]

class Solution {
public:bool find132pattern(vector<int>& nums) {if(nums.size() < 3)return false;int max_third = 0x80000000;stack<int> st;for(int i = nums.size() - 1; i >= 0; --i){if(nums[i] < max_third)return true;while(!st.empty() && nums[i] > st.top()){max_third = st.top();st.pop();}st.push(nums[i]);}return false;}
};

相关文章:

leetcode456 132 Pattern

给定数组&#xff0c;找到 i < j < k i < j < k i<j<k&#xff0c;使得 n u m s [ i ] < n u m s [ k ] < n u m s [ j ] nums[i] < nums[k] < nums[j] nums[i]<nums[k]<nums[j] 最开始肯定想着三重循环&#xff0c;时间复杂度 O ( n 3 )…...

WordPress外贸建站Astra免费版教程指南(2023)

在WordPress的外贸建站主题中&#xff0c;有许多备受欢迎的主题&#xff0c;如AAvada、Astra、Hello、Kadence等最佳WordPress外贸主题&#xff0c;它们都能满足建站需求并在市场上广受认可。然而&#xff0c;今天我要介绍的是一个不断颠覆建站人员思维的黑马——Astra主题。 …...

Vue之ElementUI实现登陆及注册

目录 ​编辑 前言 一、ElementUI简介 1. 什么是ElementUI 2. 使用ElementUI的优势 3. ElementUI的应用场景 二、登陆注册前端界面开发 1. 修改端口号 2. 下载ElementUI所需的js依赖 2.1 添加Element-UI模块 2.2 导入Element-UI模块 2.3 测试Element-UI是否能用 3.编…...

网络代理的多面应用:保障隐私、增强安全和数据获取

随着互联网的发展&#xff0c;网络代理在网络安全、隐私保护和数据获取方面变得日益重要。本文将深入探讨网络代理的多面应用&#xff0c;特别关注代理如何保障隐私、增强安全性以及为数据获取提供支持。 1. 代理服务器的基本原理 代理服务器是一种位于客户端和目标服务器之间…...

字节一面:深拷贝浅拷贝的区别?如何实现一个深拷贝?

前言 最近博主在字节面试中遇到这样一个面试题&#xff0c;这个问题也是前端面试的高频问题&#xff0c;我们经常需要对后端返回的数据进行处理才能渲染到页面上&#xff0c;一般我们会讲数据进行拷贝&#xff0c;在副本对象里进行处理&#xff0c;以免玷污原始数据&#xff0c…...

协议-TCP协议-基础概念02-TCP握手被拒绝-内核参数-指数退避原则-TCP窗口-TCP重传

协议-TCP协议-基础概念02-TCP握手被拒绝-TCP窗口 参考来源&#xff1a; 《极客专栏-网络排查案例课》 TCP连接都是TCP协议沟通的吗&#xff1f; 不是 如果服务端不想接受这次握手&#xff0c;它会怎么做呢&#xff1f; 内核参数中与TCP重试有关的参数(两个) -net.ipv4.tc…...

PDF文件压缩软件 PDF Squeezer mac中文版​软件特点

PDF Squeezer mac是一款macOS平台上的PDF文件压缩软件&#xff0c;可以帮助用户快速地压缩PDF文件&#xff0c;从而减小文件大小&#xff0c;使其更容易共享、存储和传输。PDF Squeezer使用先进的压缩算法&#xff0c;可以在不影响文件质量的情况下减小文件大小。 PDF Squeezer…...

VS+Qt+opencascade三维绘图stp/step/igs/stl格式图形读取显示

程序示例精选 VSQtopencascade三维绘图stp/step/igs/stl格式图形读取显示 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《VSQtopencascade三维绘图stp/step/igs/stl格式图形读取显示》编写…...

如何在Ubuntu中切换root用户和普通用户

问题 大家在新装Ubuntu之后&#xff0c;有没有发现自己进入不了root用户&#xff0c;su root后输入密码根本进入不了&#xff0c;这怎么回事呢&#xff1f; 打开Ubuntu命令终端&#xff1b; 输入命令&#xff1a;su root&#xff1b; 回车提示输入密码&#xff1b; 提示&…...

从零开始之了解电机及其控制(10)空间矢量理论

与一维数字转子位置不同&#xff0c;电流和电压都是二维的。可以在矩形笛卡尔平面中考虑这些尺寸。 用旋转角度和幅度来描述向量 虽然电流命令的幅度和施加的电压是进入控制器的误差项的函数&#xff0c;它们施加的角度是 d-q 轴方向的函数&#xff0c;因此也是转子位置的函数。…...

PSINS工具箱学习(一)下载安装初始化、SINS-GPS组合导航仿真、习惯约定与常用变量符号、数据导入转换、绘图显示

原始 Markdown文档、Visio流程图、XMind思维导图见&#xff1a;https://github.com/LiZhengXiao99/Navigation-Learning 文章目录 一、前言二、相关资源三、下载安装初始化1、下载PSINSyymmdd.rar工具箱文件2、解压文件3、初始化4、启动工具箱导览 四、习惯约定与常用变量符号1…...

国庆day1---消息队列实现进程之间通信方式代码,现象

snd&#xff1a; #include <myhead.h>#define ERR_MSG(msg) do{\fprintf(stderr,"__%d__:",__LINE__);\perror(msg);\ }while(0)typedef struct{ long msgtype; //消息类型char data[1024]; //消息正文 }Msg;#define SIZE sizeof(Msg)-sizeof(long)int main…...

wdb_2018_2nd_easyfmt

wdb_2018_2nd_easyfmt Arch: i386-32-little RELRO: Partial RELRO Stack: No canary found NX: NX enabled PIE: No PIE (0x8047000)32位只开了NX 这题get到一点小知识&#xff08;看我exp就知道了 int __cdecl __noreturn main(int argc, const char…...

服务器数据恢复-zfs下raidz多块磁盘离线导致服务器崩溃的数据恢复案例

服务器数据恢复环境&#xff1a; 一台服务器共配备32块硬盘&#xff0c;组建了4组RAIDZ&#xff0c;Windows操作系统zfs文件系统。 服务器故障&#xff1a; 服务器在运行过程中突然崩溃&#xff0c;经过初步检测检测没有发现服务器存在物理故障&#xff0c;重启服务器后故障依…...

云服务器 CentOS7 操作系统上安装Jpress (Tomcat 部署项目)

1、xShell 和 xftp 下载安装&#xff08;略&#xff09; https://www.xshell.com/zh/free-for-home-school/2、xftp 连接云服务器 xftp 新建连接 3、JDK 压缩包下载 下载 jdk1.8 注&#xff1a;此处 CentOS7 是64位&#xff0c;所以下载的是&#xff1a;Linux x64&#xf…...

【Linux】完美解决ubuntu18.04下vi不能使用方向键和退格键

今天在刚安装完ubuntu18.04&#xff0c;发现在使用vi命令配置文件时使用方向键并不能移动光标&#xff0c;而是出现一堆奇怪的英文字母&#xff0c;使用退格键也不能正常地删除内容&#xff0c;用惯了CentOS的我已经感觉到ubuntu没有centos用着丝滑&#xff0c;但是没办法&…...

Android studio “Layout Inspector“工具在Android14 userdebug设备无法正常使用

背景描述 做rom开发的都知道&#xff0c;“Layout Inspector”和“Attach Debugger to Android Process”是studio里很好用的工具&#xff0c;可以用来查看布局、调试系统进程&#xff08;比如setting、launcher、systemui&#xff09;。 问题描述 最进刚开始一个Android 14…...

Kafka(一)使用Docker Compose安装单机Kafka以及Kafka UI

文章目录 Kafka中涉及到的术语Kafka镜像选择Kafka UI镜像选择Docker Compose文件Kafka配置项说明KRaft vs Zookeeper和KRaft有关的配置关于Controller和Broker的概念解释Listener的各种配置 Kafka UI配置项说明 测试Kafka集群Docker Compose示例配置 Kafka中涉及到的术语 对于…...

网络知识点之-MSTP平台

本文章已收录至《网络》专栏&#xff0c;点进右上角专栏图标可访问本专栏 多业务传送平台(MSTP)技术是指基于SDH平台&#xff0c;同时实现TDM、ATM、以太网等业务的接入、处理和传送&#xff0c;提供统一网管的多业务传送平台。 MSTP充分利用SDH技术&#xff0c;特别是保护恢复…...

Azure AD混合部署,通过 Intune 管理设备,实现条件访问

需求&#xff1a; 公司要求&#xff0c;非公司设备不允许使用 邮箱&#xff0c;Teams等O365服务。 我们可以通过 Intune 中的 "条件访问" 解决这个问题。 一、设备同步到 AAD 1、配置 AAD Connect 2、选择 3、下一步 4、配置本地 企业管理员 5、配置成功 二、设备…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...