思想
首先预处理出每一个数右边的最小值用来最后判断num[d]是否存在。然后在exist()函数中使用单调栈的方法找到小于num[b]的最大num[a],然后根据num[a]找num[c]。如果num[c]右边有更小的数就返回true。
代码
import java.io.*;
import java.util.Stack;
import java.util.Arrays;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 500010, INF = Integer.MIN_VALUE, n;
static int[] num = new int[N];
static int[] min_r = new int[N]; //min_r[i]代表第i个数右边的最小值
public static void main(String[] args)throws IOException{
n = nextInt();
for(int i=0; i<n; i++) num[i] = nextInt();
//预处理min_r数组
Arrays.fill(min_r, INF);
for(int i=n-2; i>=0; i--) min_r[i] = Math.min(min_r[i+1], num[i+1]);
out.println(exist()?"YES":"NO");
out.flush();
out.close();
}
public static boolean exist(){
Stack<Integer> st =new Stack<>();
//k代表当前找到的num[i]
int k = Integer.MIN_VALUE;
//用单调栈求num[c]<num[a]<num[b]的情况
for(int i=0; i<n; i++){
//找到的条件
if(num[i]<k){
//如果c的右边存在d,使得num[d]<num[c],就结束,否则继续找
if(num[i]>min_r[i]) return true;
}
while(!st.empty() && st.peek()<num[i]){
k = Math.max(k, st.peek()); //找最大的小于num[b]的数
st.pop();
}
st.push(num[i]);
}
return false;
}
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
}