【算法|贪心算法系列No.3】leetcode334. 递增的三元子序列

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步

点击直接跳转到该题目

目录

  • 1️⃣题目描述
  • 2️⃣题目解析
  • 3️⃣解题代码

1️⃣题目描述

给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false

示例一:

输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意

示例二:

输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组

示例三:

输入:nums = [2,1,5,0,4,6]
输出:true
解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

注意:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

2️⃣题目解析

解题思路:
1.使用两个变量a和b来存储当前的最小值和次小值,初始时将a设置为数组中的第一个元素,将b设置为整型最大值。

2.遍历数组,对于每个元素nums[i],判断它是否大于b。如果是,说明找到了递增的三元组,直接返回true。

3.如果nums[i]不大于b,则判断是否大于a。如果是,更新b为nums[i],以保证b始终是当前的次小值。

4.如果nums[i]既不大于b,也不大于a,则将a更新为nums[i],以保证a始终是当前的最小值。
如果遍历完整个数组都没有找到递增的三元组,则返回false。

本题的贪心策略贪心的核心思想是尽量保持a和b的值最小,以便有更大的机会找到递增的三元组。

3️⃣解题代码

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int a = nums[0];int b = INT_MAX;for(int i = 1;i < nums.size();i++){if(nums[i] > b) return true;else if(nums[i] > a) b = nums[i];else a = nums[i];}return false;}
};

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/145926.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C语言】【结构体的位段】位段的内存分配及注意事项

1.什么是位段&#xff1a; struct A { int _a:2; int _b:5; int _c:10; int _d:30; };1.A就是一个位段类型的变量&#xff0c;位表示比特位&#xff0c;意思是 A中的变量申请内存的比特位数 比如 _a要占 2 个bit 2.位段的成员必须是 int ,unsigned int ,signed int 类型的&…

DataBinding双向绑定简介

一、简介 在Vue中使用的是MVVM架构。通过ViewModel可以实现M层和V层数据的双向绑定。Model层的数据发生变化后&#xff0c;会自动更新View层UI。UI层数据发生变化&#xff08;用户输入&#xff09;&#xff0c;可以驱动Model层的数据发生变化&#xff0c;借助于Vue框架中的View…

USART串口协议

通信接口 •通信的目的&#xff1a;将一个设备的数据传送到另一个设备&#xff0c;扩展硬件系统 • 通信协议&#xff1a;制定通信的规则&#xff0c;通信双方按照协议规则进行数据收发 全双工&#xff1a;指通信双方能够同时进行双向通信&#xff0c;一般来说&#xff0c;全双…

QT的ui设计中改变样式表的用法

在QT的ui设计中,我们右键会弹出一个改变样式表的选项,很多人不知道这个是干什么的。 首先我们来看下具体的界面 首先我们说一下这个功能具体是干嘛的, 我们在设置很多控件在界面上之后,常常都是使用系统默认的样式,但是当有些时候为了美化界面我们需要对一些控件进行美化…

计算机竞赛 深度学习手势识别 - yolo python opencv cnn 机器视觉

文章目录 0 前言1 课题背景2 卷积神经网络2.1卷积层2.2 池化层2.3 激活函数2.4 全连接层2.5 使用tensorflow中keras模块实现卷积神经网络 3 YOLOV53.1 网络架构图3.2 输入端3.3 基准网络3.4 Neck网络3.5 Head输出层 4 数据集准备4.1 数据标注简介4.2 数据保存 5 模型训练5.1 修…

数据结构:复杂度分析

目录 1 算法效率评估 1.1 实际测试 1.2 理论估算 2 迭代与递归 2.1 迭代 1. for 循环 2. while 循环 3. 嵌套循环 2.2 递归 1. 调用栈 2. 尾递归 3. 递归树 2.3 两者对比 3 时间复杂度 3.1 统计时间增长趋势 3.2 函数渐近上界…

SpringBoot整合RabbitMQ实现延迟队列功能

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…

【vue3】toRef与toRefs的使用,toRef与ref的区别

假期第四篇&#xff0c;对于基础的知识点&#xff0c;我感觉自己还是很薄弱的。 趁着假期&#xff0c;再去复习一遍 1、toRef与toRefs 创建一个ref对象&#xff0c;其value值指向另一个对象中的某个属性 语法&#xff1a;const name toRef&#xff08;person,‘name’&#xf…

期权定价模型系列【7】:Barone-Adesi-Whaley定价模型

期权定价模型系列第7篇文章 1.前言 目前大连商品交易所、郑州商品交易所、以及上海期货交易所的所有商品期权都为美式期权&#xff0c;并且大商所的所有期权合约会根据BAW(Barone-Adesi-Whaley)美式期权定价模型计算新上市期权合约的挂牌基准价。 BAW模型(Barone-Adesi and W…

动态规划算法(1)--矩阵连乘和凸多边形剖分

目录 一、动态数组 1、创建动态数组 2、添加元素 3、删除修改元素 4、访问元素 5、返回数组长度 6、for each遍历数组 二、输入多个数字 1、正则表达式 2、has.next()方法 三、矩阵连乘 1、什么是矩阵连乘&#xff1f; 2、动态规划思路 3、手推m和s矩阵 4、完…

Vue之transition组件

Vue提供了transition组件&#xff0c;使用户可以更便捷地添加过渡动画效果。 transition组件 transition组件也是一个抽象组件&#xff0c;并不会渲染出真实dom。Vue会在其第一个真实子元素上添加过渡效果。 props render 这里将render分为两部分&#xff0c;第一部分界定真…

skywalking源码本地编译运行经验总结

前言 最近工作原因在弄skywalking&#xff0c;为了进一步熟悉拉了代码下来准备debug&#xff0c;但是编译启动项目我就费了老大劲了&#xff0c;所以准备写这篇&#xff0c;帮兄弟们少踩点坑。 正确步骤 既然是用开源的东西&#xff0c;那么最好就是按照人家的方式使用&…

云服务器租用价格表概览_阿里云腾讯云华为云

云服务器租用价格多少钱一年&#xff1f;阿腾云分享阿里云、腾讯云和华为云的云服务器租用价格表&#xff1a;阿里云2核2G服务器108元一年起、腾讯云2核2G3M带宽轻量服务器95元一年、华为云2核2G3M云耀L实例89元一年起&#xff0c;阿腾云分享更多关于云服务器租用价格明细&…

PICO首届XR开发者挑战赛正式启动,助推行业迈入“VR+MR”新阶段

9月25日&#xff0c;“PICO 2023首届XR开发者挑战赛”&#xff08;下文简称“挑战赛”&#xff09;媒体启动会在北京圆满落幕&#xff0c;官方赛事报名通道已于今日开启。据悉&#xff0c;本次挑战赛是PICO首次针对全球开发者举办的大型挑战赛事&#xff0c;旨在与开发者保持连…

第1篇 目标检测概述 —(4)目标检测评价指标

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。目标检测评价指标是用来衡量目标检测算法性能的指标&#xff0c;可以分为两类&#xff0c;包括框级别评价指标和像素级别评价指标。本节课就给大家重点介绍下目标检测中的相关评价指标及其含义&#xff0c;希望大家学习之后…

15np+pandas+matplotlib

numpy 维数 一维:shape(4,)二维:shape(4,5)三维:shape(4,5,6) 创建ndarray–np.array() # 可以是数组[1,2,3] 元组(1,2,3) 迭代对象range(n) np.array([1,2,3,4,5])列表中元素类型不同&#xff0c;会使用元素类型最大的作为ndarray类型 指定维度ndim 赋值操作 赋值&#xff…

NLP 01(介绍)

一、NLP 自然语言处理 (Natural Language rrocessing,简称NLP) 是计算机科学与语言学中关注于计算机与人类语言间转换的领域。 1.1 发展 规则&#xff1a;基于语法 自然语言处理的应用场景: 语音助手 机器翻译 搜索引擎 智能问答

独立按键控制LED亮灭、独立按键控制LED状态、独立按键控制LED显示二进制、独立按键控制LED移位——“51单片机”

各位CSDN的uu们你们好呀&#xff0c;今天依旧是小雅兰的51单片机的内容&#xff0c;内容主要是&#xff1a;独立按键控制LED亮灭、独立按键控制LED状态、独立按键控制LED显示二进制、独立按键控制LED移位&#xff0c;下面&#xff0c;让我们进入51单片机的世界吧&#xff01;&a…

基于Qt Creator开发的坦克大战小游戏

目录 介绍开发环境技术介绍安装说明项目目录设计思想项目介绍运行演示知识点记录Gitee源码链接 介绍 &#xff01;&#xff01;&#xff01;资源图片是从网上免费下载&#xff0c;源码都是原创&#xff0c;供个人学习使用&#xff0c;非盈利&#xff01;&#xff01;&#xff…

Elastic SQL 输入:数据库指标可观测性的通用解决方案

作者&#xff1a;Lalit Satapathy, Ishleen Kaur, Muthukumar Paramasivam Elastic SQL 输入&#xff08;metricbeat 模块和输入包&#xff09;允许用户以灵活的方式对许多支持的数据库执行 SQL 查询&#xff0c;并将结果指标提取到 Elasticsearch。 本博客深入探讨了通用 SQL …