四元组问题
问题描述
从小学开始，小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期，他遇到了一个非常有趣的问题，那就是给定一个长度为 nn 的整数数组 numsnums ，判断是否存在四个不同的下标 a,b,c,da,b,c,d ，使得 aa < bb < cc < dd ，并且 nums[d]nums[d] < nums[c]nums[c] < nums[a]nums[a] < nums[b]nums[b] 。
小明非常喜欢这个问题，他决定用数学的方式来解决它。他首先想到了一个非常简单的方法，那就是暴力枚举。他用四个循环来枚举所有可能的下标组合，然后判断是否满足条件。但是这个方法非常耗时，当 nn 很大时，计算量会非常大。
所以请求你给出一个快速智慧的解决办法。
输入格式
输入仅两行，第一行包含一个整数 nn ，第二行包含 nn 个整数，其含义如上所述。
输出格式
输出仅一行，包含一个字符串，YES表示题目存在上面所描述的情况，否则输出NO。
样例输入
4 3 4 2 1样例输出
YES说明
在样例中，当 a,b,c,da,b,c,d 分别等于 0,1,2,30,1,2,3 满足 aa < bb < cc < dd ，并且使得 nums[d]nums[d] < nums[c]nums[c] < nums[a]nums[a] < nums[b]nums[b] 。
评测数据规模
对于 5050% 的评测数据， 4≤n≤200，−200≤nums[i]≤2004≤n≤200，−200≤nums[i]≤200 。
对于 100100% 的评测数据，4≤n≤5×105，−109≤nums[i]≤1094≤n≤5×105，−109≤nums[i]≤109 。
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N=5*100010; static int a[]=new int[N]; static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(st.nextToken()); } //nums[d] < nums[c] < nums[a] < nums[b] //对于c而言 我想知道我的右侧是否有比我小的数 int rightMin[]=new int[n+1];//维护一个后缀最小值 rightMin[n]=n; for (int i = n-1; i > 0; i--) { if(a[i]<a[rightMin[i+1]]){ rightMin[i]=i; }else{ rightMin[i]=rightMin[i+1]; } } //站在c的角度上 我迫切的想知道我的左侧是否存在两个数满足 nums[a] < nums[b] //如果说当前的模拟的c< 我的左侧所有数中 次大的数时 说明我找到了 nums[c] < nums[a] < nums[b] 这样一种关系 //因为四大的数找到了，那么必然存在一个比它大的数 //我们维护一个单调递减的栈 当栈顶的元素小于我遍历到的数时 我们就找到了一个 nums[a] < nums[b]这样的序列 //这时我们将num[a] 也就是次大值poll并记录该值 max2 int max2=Integer.MIN_VALUE;; Deque<Integer> deque=new LinkedList<Integer>(); boolean f=false; for (int i = 1; i <= n; i++) { int u=a[i]; //将当前数作为c 看是否符合条件 if(u<max2 && u<rightMin[i]){ bw.write("YES"); f=true; break; } //当前的数可以用于更新max2 我们记录最大的max2 是为了使得更多的c更有可能满足条件 while(!deque.isEmpty() && deque.peekLast()<u)max2=Math.max(max2, deque.pollLast()); deque.add(u); } if(!f)bw.write("NO"); br.close(); bw.flush(); bw.close(); } }
