单调栈-四元组问题

四元组问题问题描述从小学开始小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期他遇到了一个非常有趣的问题那就是给定一个长度为 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 N5*100010; static int a[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew 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[n1];//维护一个后缀最小值 rightMin[n]n; for (int i n-1; i 0; i--) { if(a[i]a[rightMin[i1]]){ rightMin[i]i; }else{ rightMin[i]rightMin[i1]; } } //站在c的角度上 我迫切的想知道我的左侧是否存在两个数满足 nums[a] nums[b] //如果说当前的模拟的c 我的左侧所有数中 次大的数时 说明我找到了 nums[c] nums[a] nums[b] 这样一种关系 //因为四大的数找到了那么必然存在一个比它大的数 //我们维护一个单调递减的栈 当栈顶的元素小于我遍历到的数时 我们就找到了一个 nums[a] nums[b]这样的序列 //这时我们将num[a] 也就是次大值poll并记录该值 max2 int max2Integer.MIN_VALUE;; DequeInteger dequenew LinkedListInteger(); boolean ffalse; for (int i 1; i n; i) { int ua[i]; //将当前数作为c 看是否符合条件 if(umax2 urightMin[i]){ bw.write(YES); ftrue; break; } //当前的数可以用于更新max2 我们记录最大的max2 是为了使得更多的c更有可能满足条件 while(!deque.isEmpty() deque.peekLast()u)max2Math.max(max2, deque.pollLast()); deque.add(u); } if(!f)bw.write(NO); br.close(); bw.flush(); bw.close(); } }