Verán, he estado aprendiendo y practicando programación competitiva, y en un problema de un concurso tenía que hacer una búsqueda en un arreglo bidireccional. Hice lo primero que pensé, una búsqueda anidada y contadores pero solo obtuve el 75% correcto de los casos. Cuando dieron las soluciones, en ese problema solo mencionaron que se usa una estructura de datos de la cual no supe descifrar el hombre porque es muy raro, recuerdo escuchar "monotonons jack". Quisiera ver si alguien me pudiera decir si existe esta estructura de datos o una parecida.
Aquí el código que hice (en java) y las indicaciones del problema: Limite de Memoria: 32MiB Limite de tiempo por caso: 500 ms Limite de tiempo total: 1 min
Entrada
Un entero N seguido de las N alturas de los edificios. Puedes suponer que 0≤N≤1050≤N≤105 y que las alturas de los edificios son distintas y en el rango de 11 a 109109.
Salida
Para cada edificio, la cantidad de azoteas que puedes ver desde ahí.
Ejemplo
Entrada
6
7 1 4 3 5 2
Salida
6 1 3 1 5 1
codigo
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class edificio {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
int veces = Integer.parseInt(br.readLine());
String cad = br.readLine();
StringTokenizer st = new StringTokenizer(cad, " ");
ArrayList<Integer> v1 = new ArrayList<>();
ArrayList<Integer> v2 = new ArrayList<>();
for (int i = 0; i < veces; i++) {
v1.add(Integer.parseInt(st.nextToken()));
}
int cont = 0, cont2;
for (int i = 0; i < v1.size(); i++) {
for (int j = i; j < v1.size(); j++) {
if (v1.get(i) >= v1.get(j)) {
cont++;
} else {
break;
}
}
cont2 = cont;
cont = 0;
for (int j = i - 1; j >= 0; j--) {
if (j >= 0 && j <= v1.size()) {
if (v1.get(i) > v1.get(j)) {
cont2++;
} else {
break;
}
} else {
break;
}
}
v2.add(cont2);
}
System.out.println(v2);
} catch (Exception e) {
}
}
}