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

四元组问题

目录

问题描述

输入格式

输出格式

样例输入

样例输出

说明

评测数据规模

运行限制

原题链接

代码思路


问题描述

从小学开始,小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期,他遇到了一个非常有趣的问题,那就是给定一个长度为 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++1s512M
C1s512M
Java2s512M
Python33s512M
PyPy33s512M
Go3s64M
JavaScript3s64M

原题链接

四元组问题icon-default.png?t=O83Ahttps://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");}
}

相关文章:

四元组问题

目录 问题描述 输入格式 输出格式 样例输入 样例输出 说明 评测数据规模 运行限制 原题链接 代码思路 问题描述 从小学开始&#xff0c;小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期&#xff0c;他遇到了一个非常有趣的问题&…...

如何用Prometheus监控禁用了Actuator的SpringBoot?

需求来源 prometheus监控微服务一般都是使用micrometer结合actuator来做&#xff1a; 添加依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId> </dependency> <d…...

使用TensorFlow实现一个简单的神经网络:从入门到精通

使用TensorFlow实现一个简单的神经网络:从入门到精通 在现代数据科学和机器学习领域,神经网络是一个非常重要的工具。TensorFlow 是一个开源的深度学习框架,由 Google 开发和维护,它使得构建和训练神经网络变得更加容易。本文将详细介绍如何使用 TensorFlow 实现一个简单的…...

应用DFX能力介绍

一、HarmonyOS生态DFX能力范围 围绕开发者&#xff0c;构建三方应用和设备从开发到维护全生命周期所必需、有竞争力、有特色的调试调优、定位、维护能力。 二、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命令&#xff08;临时配置&#xff09;Debian/Ubuntu系统&#xff08;使用netplan&#xff09;CentOS/RHEL系统&#xff08;使用nmcli或nmtui&#xff09;使用nmcli&#xff08;命令行界面&#xff09;使用nmtui&#xff08;文本用户界面&#xff09;通过图形界…...

Dependency Check:一款针对应用程序依赖组件的安全检测工具

关于Dependency Check Dependency-Check 是一款软件组合分析 &#xff08;SCA&#xff09; 工具&#xff0c;可尝试检测项目依赖项中包含的公开披露的漏洞。它通过确定给定依赖项是否存在通用平台枚举 &#xff08;CPE&#xff09; 标识符来实现此目的。如果找到&#xff0c;它…...

Python 从入门到实战28(文件的读操作)

我们的目标是&#xff1a;通过这一套资料学习下来&#xff0c;通过熟练掌握python基础&#xff0c;然后结合经典实例、实践相结合&#xff0c;使我们完全掌握python&#xff0c;并做到独立完成项目开发的能力。 上篇文章我们讨论了文件的打开、创建、关闭的相关知识。今天我们将…...

[leetcode刷题]面试经典150题之7同构字符串(简单)

这个题虽然是简单题&#xff0c;但是看了半天还是没啥好思路&#xff0c;最后看了解题学到了不少知识点 1.index() 函数查找序列中首次出现的元素索引 2.zip函数&#xff1a;用于将可迭代的对象&#xff08;如列表、元组、字典等&#xff09;作为参数&#xff0c;将对象中对应…...

【Keil5教程及技巧】耗时一周精心整理万字全网最全Keil5(MDK-ARM)功能详细介绍【建议收藏-细细品尝】

&#x1f48c; 所属专栏&#xff1a;【单片机开发软件技巧】 &#x1f600; 作  者&#xff1a; 于晓超 &#x1f680; 个人简介&#xff1a;嵌入式工程师&#xff0c;专注嵌入式领域基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大家&#xff1…...

【rust】 基于rust编写wasm,实现markdown转换为html文本

文章目录 背景转换预览核心代码前置依赖rustup换源cargo换源中科大 wasm-pack安装 背景 尝试用rust编写一款markdown转html的插件&#xff0c;通过wasm给html使用&#xff0c;不得不说体积挺小&#xff0c;约200K&#xff0c; 比go的wasm起步2MB看着舒服点。 不过go的配置和换…...

Java中的反向代理与负载均衡:Nginx与Java服务的集成

Java中的反向代理与负载均衡&#xff1a;Nginx与Java服务的集成 大家好&#xff0c;我是微赚淘客返利系统3.0的小编&#xff0c;是个冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们来探讨一下Java应用中的反向代理与负载均衡&#xff0c;以及如何通过Ngin…...

高级java每日一道面试题-2024年9月26日-运维篇[分布式篇]-如何保证每个服务器的时间都是同步的?

如果有遗漏,评论区告诉我进行补充 面试官: 如何保证每个服务器的时间都是同步的? 我回答: 确保服务器之间的时间同步对于维护分布式系统的一致性、日志记录的准确性以及安全认证的有效性非常重要。以下是几种常见的方法来保证服务器时间同步&#xff1a; 1. 使用NTP&#…...

探索MemGPT:AI界的新宠儿

文章目录 探索MemGPT&#xff1a;AI界的新宠儿1. 背景介绍2. MemGPT是什么&#xff1f;3. 如何安装MemGPT&#xff1f;4. 简单的库函数使用方法5. 场景应用场景一&#xff1a;创建持久聊天机器人场景二&#xff1a;文档分析场景三&#xff1a;多会话聊天互动 6. 常见Bug及解决方…...

处理RabbitMQ连接和认证问题

在使用RabbitMQ进行消息队列管理时&#xff0c;我们可能会遇到各种连接和认证问题。本文将介绍如何诊断和解决这些问题&#xff0c;并通过使用RabbitMQ的管理端进行登录验证来确保配置正确。 1. 问题概述 在最近的一次部署中&#xff0c;我们遇到了两个主要问题&#xff1a; …...

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()吗&#xff1f; 你知道下面代码的输出结果吗&#xff1f; int a123; printf("%2d \n",a); printf() 函数是 C 语言中用于格式化输出的标准函数&#xff0c;它允许你将数据以特定的格式输出到标准输出设备&#xff08;通常是屏幕&#xff09;。p…...

编译win2k3中tools目录下i386mk.inc文件的作用

编译win2k3中tools目录下i386mk.inc文件的作用 在Windows Driver Kit&#xff08;WDK&#xff09;的根安装目录下&#xff0c;这些文件存储在bin子目录中。 在这些文件中&#xff0c;有特定于该目标的优化规则或汇编指令。可能还需要额外的链接标志、资源编译器标志或C预处理器…...

IPSec隧道协议学习(一)

前情回顾 前面介绍的GRE隧道协议&#xff0c;可以字LAN之间通过Internet建立隧道&#xff0c;实现网络间资源共享&#xff0c;但是GRE隧道协议不能实现加密功能&#xff0c;传输的数据不受加密保护&#xff0c;为了实现在隧道间传输数据包收到加密保护&#xff0c;需要使用IPS…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...