四元组问题

目录

问题描述

输入格式

输出格式

样例输入

样例输出

说明

评测数据规模

运行限制

原题链接

代码思路

---

问题描述

从小学开始，小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期，他遇到了一个非常有趣的问题，那就是给定一个长度为 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");}
}