四元组问题
目录
问题描述
输入格式
输出格式
样例输入
样例输出
说明
评测数据规模
运行限制
原题链接
代码思路
问题描述
从小学开始,小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期,他遇到了一个非常有趣的问题,那就是给定一个长度为 n 的整数数组 nums ,判断是否存在四个不同的下标 a,b,c,d ,使得 a < b < c < d ,并且 nums[d] < nums[c] < nums[a] < nums[b] 。
小明非常喜欢这个问题,他决定用数学的方式来解决它。他首先想到了一个非常简单的方法,那就是暴力枚举。他用四个循环来枚举所有可能的下标组合,然后判断是否满足条件。但是这个方法非常耗时,当 n 很大时,计算量会非常大。
所以请求你给出一个快速智慧的解决办法。
输入格式
输入仅两行,第一行包含一个整数 n ,第二行包含 n 个整数,其含义如上所述。
输出格式
输出仅一行,包含一个字符串, YES 表示题目存在上面所描述的情况,否则输出 NO 。
样例输入
4
3 4 2 1
样例输出
YES
说明
在样例中,当 a,b,c,d 分别等于 0,1,2,3 满足 a < b < c < d ,并且使得 nums[d] < nums[c] < nums[a] < nums[b]。
评测数据规模
对于 50% 的评测数据,4≤n≤200,−200≤nums[i]≤200 。
对于 100% 的评测数据,4≤n≤5×105,−109≤nums[i]≤109 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 512M |
| C | 1s | 512M |
| Java | 2s | 512M |
| Python3 | 3s | 512M |
| PyPy3 | 3s | 512M |
| Go | 3s | 64M |
| JavaScript | 3s | 64M |
原题链接
四元组问题
https://www.lanqiao.cn/problems/3416/learning/
代码思路
import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int nums[] = new int[n];// smnum数组中每个值代表num[i]后面的最小的数.// 如:smnum[i]的值是num[i]后面的最小的数.int smnum[] = new int[n];for (int i = 0; i < nums.length; i++) {nums[i] = scanner.nextInt();}smnum[n - 1] = Integer.MAX_VALUE;// 因为题目中最大索引的值反而最小,所以要倒序.for (int i = n - 1; i >= 1; i--) {smnum[i - 1] = Math.min(smnum[i], nums[i]);}int a = Integer.MIN_VALUE;// 用先进后出的栈也可以,用先进先出的队列也可以,,但用栈符合一般的逻辑习惯.// 上面的理由是这一步stack.peek() < nums[i],提供的.Stack<Integer> stack = new Stack<Integer>();for (int i = 0; i < nums.length; i++) {// 题中要求是 nums[d] < nums[c] < nums[a] < nums[b]// 与上面的一一对应 smnum[i] nums[i] a 栈里的元素if (a > nums[i] && nums[i] > smnum[i]) {System.out.println("YES");return;}while (!stack.isEmpty() && stack.peek() < nums[i]) {// 因为a的值都是小于nums[i]的,所以栈里必有索引小于i且值大于a的.// pop()出栈,是为了提高效率.// 要是使用peek(),会超时.a = Math.max(a, stack.pop());}stack.push(nums[i]);}// 没return,则输出NO.System.out.println("NO");}
}
相关文章:
四元组问题
目录 问题描述 输入格式 输出格式 样例输入 样例输出 说明 评测数据规模 运行限制 原题链接 代码思路 问题描述 从小学开始,小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期,他遇到了一个非常有趣的问题&…...
如何用Prometheus监控禁用了Actuator的SpringBoot?
需求来源 prometheus监控微服务一般都是使用micrometer结合actuator来做: 添加依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId> </dependency> <d…...
使用TensorFlow实现一个简单的神经网络:从入门到精通
使用TensorFlow实现一个简单的神经网络:从入门到精通 在现代数据科学和机器学习领域,神经网络是一个非常重要的工具。TensorFlow 是一个开源的深度学习框架,由 Google 开发和维护,它使得构建和训练神经网络变得更加容易。本文将详细介绍如何使用 TensorFlow 实现一个简单的…...
应用DFX能力介绍
一、HarmonyOS生态DFX能力范围 围绕开发者,构建三方应用和设备从开发到维护全生命周期所必需、有竞争力、有特色的调试调优、定位、维护能力。 二、HarmonyOS DFX能力全集 三、DFX设计主要范围 1、HiLog 日志分类 日志常用命令 日志级别 日志规则 2、HiAppEvent 完…...
第三篇 第20章工程计价数字化与智能化
第三篇 工程计价 第20章 工程计价数字化与智能化 20.1 BIM在工程计价中的应用 20.1.1 BIM概述 1.定义 在建设工程及设施全生命周期内,对其物理特征和功能特征信息进行数字化表达,依次设计、施工、运营的过程和结果的总称。应由核心层、共享层、专业领域层、资源层四个概念层…...
成语700词(46~65组)
目录 46.熟悉、了解、知晓相关(15 个)47.很常见不奇怪(6 个)48.看法一致与否(10 个)49.从细节看全貌(10 个)50.看事情透彻(11 个)51.对事情的态度与评价(7 个)52.数量多与少(11 个)53.建筑相关(6 个)54.相同与不同(17 个)55.技艺精湛(10 个)56.与观看欣赏相…...
linux如何配置静态IP
文章目录 使用ip命令(临时配置)Debian/Ubuntu系统(使用netplan)CentOS/RHEL系统(使用nmcli或nmtui)使用nmcli(命令行界面)使用nmtui(文本用户界面)通过图形界…...
Dependency Check:一款针对应用程序依赖组件的安全检测工具
关于Dependency Check Dependency-Check 是一款软件组合分析 (SCA) 工具,可尝试检测项目依赖项中包含的公开披露的漏洞。它通过确定给定依赖项是否存在通用平台枚举 (CPE) 标识符来实现此目的。如果找到,它…...
Python 从入门到实战28(文件的读操作)
我们的目标是:通过这一套资料学习下来,通过熟练掌握python基础,然后结合经典实例、实践相结合,使我们完全掌握python,并做到独立完成项目开发的能力。 上篇文章我们讨论了文件的打开、创建、关闭的相关知识。今天我们将…...
[leetcode刷题]面试经典150题之7同构字符串(简单)
这个题虽然是简单题,但是看了半天还是没啥好思路,最后看了解题学到了不少知识点 1.index() 函数查找序列中首次出现的元素索引 2.zip函数:用于将可迭代的对象(如列表、元组、字典等)作为参数,将对象中对应…...
【Keil5教程及技巧】耗时一周精心整理万字全网最全Keil5(MDK-ARM)功能详细介绍【建议收藏-细细品尝】
💌 所属专栏:【单片机开发软件技巧】 😀 作 者: 于晓超 🚀 个人简介:嵌入式工程师,专注嵌入式领域基础和实战分享 ,欢迎咨询! 💖 欢迎大家࿱…...
【rust】 基于rust编写wasm,实现markdown转换为html文本
文章目录 背景转换预览核心代码前置依赖rustup换源cargo换源中科大 wasm-pack安装 背景 尝试用rust编写一款markdown转html的插件,通过wasm给html使用,不得不说体积挺小,约200K, 比go的wasm起步2MB看着舒服点。 不过go的配置和换…...
Java中的反向代理与负载均衡:Nginx与Java服务的集成
Java中的反向代理与负载均衡:Nginx与Java服务的集成 大家好,我是微赚淘客返利系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿!今天我们来探讨一下Java应用中的反向代理与负载均衡,以及如何通过Ngin…...
高级java每日一道面试题-2024年9月26日-运维篇[分布式篇]-如何保证每个服务器的时间都是同步的?
如果有遗漏,评论区告诉我进行补充 面试官: 如何保证每个服务器的时间都是同步的? 我回答: 确保服务器之间的时间同步对于维护分布式系统的一致性、日志记录的准确性以及安全认证的有效性非常重要。以下是几种常见的方法来保证服务器时间同步: 1. 使用NTP&#…...
探索MemGPT:AI界的新宠儿
文章目录 探索MemGPT:AI界的新宠儿1. 背景介绍2. MemGPT是什么?3. 如何安装MemGPT?4. 简单的库函数使用方法5. 场景应用场景一:创建持久聊天机器人场景二:文档分析场景三:多会话聊天互动 6. 常见Bug及解决方…...
处理RabbitMQ连接和认证问题
在使用RabbitMQ进行消息队列管理时,我们可能会遇到各种连接和认证问题。本文将介绍如何诊断和解决这些问题,并通过使用RabbitMQ的管理端进行登录验证来确保配置正确。 1. 问题概述 在最近的一次部署中,我们遇到了两个主要问题: …...
FFmpeg中结构释放小函数
用于FFmpeg一些结构内存释放问题 #pragma once #include <iostream>extern "C" { #include "libavformat/avformat.h" #include "libavcodec/avcodec.h" #include "libavutil/avutil.h" #include "libavutil/frame.h"…...
C语言中的一些小知识(三)
一、你了解printf()吗? 你知道下面代码的输出结果吗? int a123; printf("%2d \n",a); printf() 函数是 C 语言中用于格式化输出的标准函数,它允许你将数据以特定的格式输出到标准输出设备(通常是屏幕)。p…...
编译win2k3中tools目录下i386mk.inc文件的作用
编译win2k3中tools目录下i386mk.inc文件的作用 在Windows Driver Kit(WDK)的根安装目录下,这些文件存储在bin子目录中。 在这些文件中,有特定于该目标的优化规则或汇编指令。可能还需要额外的链接标志、资源编译器标志或C预处理器…...
IPSec隧道协议学习(一)
前情回顾 前面介绍的GRE隧道协议,可以字LAN之间通过Internet建立隧道,实现网络间资源共享,但是GRE隧道协议不能实现加密功能,传输的数据不受加密保护,为了实现在隧道间传输数据包收到加密保护,需要使用IPS…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
