四元组问题
import java.util.*;
public class Main {
static final int N = 500010;
static int[] a = new int[N], l = new int[N], r = new int[N];
static int n;
/*
在序列中寻找一个形如该形状的一段
枚举每一个b找左边第一个比b小的
找右边第一个比b小的并且比a小的
再找一个d比c小即可
考虑单调栈,倒序遍历先枚举保证可以连续找两个右边的
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
Stack<Integer> stk1 = new Stack<>();//左
for (int i = 1; i <= n; i++) {
//先找左边
while (!stk1.isEmpty() && a[stk1.peek()] >= a[i]) stk1.pop();
if (stk1.isEmpty()) l[i] = 0;
else l[i] = stk1.peek();
stk1.push(i);
}
Stack<Integer> stk2 = new Stack<>();//右
for (int i = n; i >= 1; i--) {
int b = a[i];
//再找右边
Stack<Integer> t = (Stack<Integer>) stk2.clone();
while (!stk2.isEmpty() && a[stk2.peek()] >= b) stk2.pop();
if (stk2.isEmpty()) r[i] = n + 1;
else r[i] = stk2.peek();
stk2.push(i);
if (l[i] == 0) continue;//判断a是否找到
while (!t.isEmpty() && a[t.peek()] >= b && a[t.peek()] < a[l[i]]) t.pop();
if (t.isEmpty()) continue;//判断c是否找到
int c = t.peek();
//在看看右边的右边是否有比c小的
if (r[c] <= n) {
System.out.println("YES");
return;
}
}
System.out.println("NO");
}
}