Compruebe si la matriz es monótona, es decir, monótono creciente o monótono decreciente
Una matriz A es monótona creciente si para todo i <= j, A [i] <= A [j]. Una matriz A es monótona decreciente si para todo i <= j, A [i]> = A [j].
Devuelve verdadero si y solo si la matriz A dada es monótona.
public class MonotonicArray {
public boolean IsMonotonic(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
if (numbers.length == 1) {
return true;
}
boolean increasing = false;
boolean decreasing = false;
for (int index = 0; index < numbers.length - 1; index++) {
if (numbers[index + 1] == numbers[index]){
continue;
}
if (numbers[index + 1] > numbers[index]) {
if (!decreasing) {
increasing = true;
} else {
return false;
}
}
else {
if (!increasing) {
decreasing = true;
} else {
return false;
}
}
}
return increasing || decreasing;
}
}
Casos de prueba:
class MonotonicArrayTest extends MonotonicArray {
@org.junit.jupiter.api.Test
void isMonotonic1() {
int[] array = new int[]{1,2,3};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic2() {
int[] array = new int[]{-1,-2,-3};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic3() {
int[] array = new int[]{1,2,1};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic4() {
int[] array = new int[]{-1,2,-9};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic5() {
int[] array = new int[]{9,3,2};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic6() {
int[] array = new int[]{};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic7() {
int[] array = new int[]{1};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic8() {
int[] array = new int[]{9,7,5,4,8,10};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic9() {
int[] array = new int[]{1,1,2,3};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic10() {
int[] array = new int[]{1,1,0,-1};
assertEquals(true,IsMonotonic(array));
}
}
Respuestas
estático
IsMonotonic(...)no necesita una instancia de la MonotonicArrayclase para funcionar, por lo tanto, debería ser estática.
Consistencia
En caso especial, una matriz de longitud 1 es monótona. ¿Es realmente? No aumenta ni disminuye.
¿Qué hay de IsMonotonic(new int[]{1, 1, 1, 1})? Me parece que debería ser así true, pero volverá false. Definitivamente debería agregarse como un caso de prueba. Y si regresara true, entonces ...
Mejoramiento
... comprobar la longitud 1 es demasiado restrictivo. Cualquier matriz de longitud 2 siempre será monótona también. Quizás:
if (numbers.length == 1) {
return true;
}
debiera ser:
if (numbers.length <= 2) {
return true;
}
Bucle
Esto es feo. ¿Java optimizará el numbers.length - 1cálculo como una constante?
for (int index = 0; index < numbers.length - 1; index++) {
if (numbers[index + 1] == numbers[index]){
continue;
}
...
Puede ser mejor usar el forbucle mejorado de Java para extraer números y confiar en un comportamiento monótono que permita la igualdad para manejar el primer elemento:
int current = numbers[0];
for(int value : numbers) {
if (value != current) {
if (value < current) {
...
} else {
...
}
current = value;
}
}
El bucle es bastante complicado. En general, es mejor usar una lógica más simple si es posible, ya que eso hace que el ciclo sea más simple de razonar. Por ejemplo, puede usar Integer.comparepara eliminar gran parte de la lógica de su ciclo.
public static boolean IsMonotonic(int[] numbers) {
int lastCmp = 0;
for (int i = 1; i < numbers.length; i++) {
int cmp = Integer.compare(numbers[i], numbers[i - 1]);
if (lastCmp == 0) {
lastCmp = cmp;
} else if (cmp != 0 && ((cmp > 0) != (lastCmp > 0))) {
return false;
}
}
return true;
}
En cada iteración, la cmpvariable es cero si los dos números son iguales, y positiva o negativa dependiendo de si hubo un aumento o una disminución.
Cuando lastCmpes cero, todavía tenemos que ver un aumento o una disminución, es decir, todos los números enteros han sido iguales. Si lastCmpes distinto de cero, entonces hemos visto un aumento o una disminución. Si la secuencia no es monótona, eventualmente llegaremos a un par que se movió en la dirección opuesta al primer cambio, que es lo que detectará la segunda condición.
Si la lista es más corta que dos elementos, entonces el ciclo no se ejecuta en absoluto y solo devuelve verdadero.
Es posible obtener un mejor rendimiento y simplicidad si se decida de inmediato: Al comparar el primer valor con el último valor inmediatamente te dice lo que uno de aumento / disminución / constante que debe comprobar.
Lo que debe hacer
nulldepende del contrato. Este problema está en LeetCode , donde incluso tiene la garantía de que la matriz tendrá al menos un elemento, por lo que no necesitaría cubrirnullni una matriz vacía. Usted "eligió" (?) Para regresarfalse, pero también podría argumentar a favortrue, ya que "sin matriz" parece bastante similar a "sin elementos", para lo cual la respuesta correcta es por ciertotrue, nofalse.
Aquí hay uno que usa una verificación de primero contra último (aunque incluí "constante" en "creciente") y que pone la carga sobre la persona que llama para proporcionar una entrada razonable (es decir, no null). Creo que es mejor que el usuario obtenga un error que pretender silenciosamente que no pasa nada.
public boolean isMonotonic(int[] numbers) {
int last = numbers.length - 1;
if (last >= 0 && numbers[0] <= numbers[last]) {
for (int i = 0; i < last; i++) {
if (numbers[i] > numbers[i+1]) {
return false;
}
}
} else {
for (int i = 0; i < last; i++) {
if (numbers[i] < numbers[i+1]) {
return false;
}
}
}
return true;
}
Una BiPredicateversión inspirada en la respuesta de RoToRa . Éste distingue los tres casos, ya que BiPredicateevita la duplicación de código:
public boolean isMonotonic(int[] numbers) {
int n = numbers.length;
if (n <= 2) {
return true;
}
BiPredicate<Integer, Integer> fail =
numbers[0] < numbers[n-1] ? (a, b) -> a > b :
numbers[0] > numbers[n-1] ? (a, b) -> a < b :
(a, b) -> a != b;
for (int i = 1; i < n; i++)
if (fail.test(numbers[i-1], numbers[i]))
return false;
return true;
}
Versión de Python, solo por diversión :-)
from operator import eq, le, ge
def isMonotonic(numbers):
first, last = numbers[:1], numbers[-1:]
check = eq if first == last else le if first < last else ge
return all(map(check, numbers, numbers[1:]))
No soy un gran admirador de tener una sola función monolítica que verifique indiscriminadamente tanto la monotonía creciente como la decreciente. En la mayoría de los escenarios prácticos, imagino que probablemente necesitaría saber si está aumentando o disminuyendo.
Basado en eso, definiría específicamente:
public static boolean isMonotonic(int[] numbers) {
return isMonotonicIncreasing(numbers) || isMonotonicDecreasing(numbers);
}
public static boolean isMonotonicIncreasing(int[] numbers) {
return isXXX(numbers, (a, b) -> a <= b); // Not sure how to call this method
}
Claro, habrá un par de comprobaciones duplicadas, pero al final, en mi opinión, el código estará mejor estructurado, será más legible y más reutilizable.
Si acepta la consistencia observación de @AJNeufeld (de modo que [1]siendo monótona indica que [1,1,1]puede ser bastante monótona también) y poner el otro comentario acerca de [x,y]ser monótona de nuevo, puede que le resulte más fácil tener true-s por defecto y reconocer cuando la matriz no es monótono:
public static boolean IsMonotonic(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
boolean inc_or_const = true;
boolean dec_or_const = true;
int prev = numbers[0];
for (int curr : numbers) {
if (curr < prev) {
inc_or_const = false;
} else if (curr > prev) {
dec_or_const = false;
}
prev = curr;
}
return inc_or_const || dec_or_const;
}
Por supuesto, se ve tan ordenado solo sin cortocircuitos, después de eso, esto tendrá una estructura muy similar a su código original nuevamente:
public static boolean IsMonotonic(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
boolean inc_or_const = true;
boolean dec_or_const = true;
int prev = numbers[0];
for (int i = 1; i < numbers.length; i++) {
int curr = numbers[i];
if (curr < prev) {
inc_or_const = false;
if (!dec_or_const) {
return false;
}
} else if (curr > prev) {
dec_or_const = false;
if (!inc_or_const) {
return false;
}
}
prev = curr;
}
return true;
}
Aquí volví al acceso indexado sobre la base de mi disgusto por comparar el primer elemento consigo mismo (lo que hace la for(:)variante). También tenga en cuenta que aquí, debido a los cortocircuitos return, la finalización del ciclo significa que la matriz es monótona con seguridad. Además, numbers.length-1también se ha aplicado el comentario sobre el peligro de tener una condición de bucle.