Проверьте, является ли массив монотонным, т.е. монотонно увеличивается или монотонно уменьшается
Массив A монотонно возрастает, если для всех i <= j, A [i] <= A [j]. Массив A монотонно убывает, если для всех i <= j, A [i]> = A [j].
Вернуть true тогда и только тогда, когда данный массив A монотонен.
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;
}
}
Тестовые случаи:
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));
}
}
Ответы
статический
IsMonotonic(...)для работы не требуется экземпляр MonotonicArrayкласса, поэтому он должен быть статическим.
Последовательность
Вы частный случай массив длины 1 как монотонный. Это правда? Он не увеличивается и не уменьшается.
О чем IsMonotonic(new int[]{1, 1, 1, 1})? Мне кажется, так и должно быть true, но вернется false. Определенно следует добавить в качестве тестового примера. А если вернется true, то ...
Оптимизация
... проверка длины 1 слишком строгая. Любой массив длины 2 всегда будет монотонным. Возможно:
if (numbers.length == 1) {
return true;
}
должно быть:
if (numbers.length <= 2) {
return true;
}
Зацикливание
Это некрасиво. Будет ли Java оптимизировать numbers.length - 1расчет как константу?
for (int index = 0; index < numbers.length - 1; index++) {
if (numbers[index + 1] == numbers[index]){
continue;
}
...
Возможно, лучше использовать расширенный forцикл Java для извлечения чисел и полагаться на монотонное поведение, позволяющее равенству обрабатывать первый элемент:
int current = numbers[0];
for(int value : numbers) {
if (value != current) {
if (value < current) {
...
} else {
...
}
current = value;
}
}
Петля довольно сложная. Как правило, по возможности лучше использовать более простую логику, так как это упрощает рассуждение о цикле. Например, вы можете использовать, Integer.compareчтобы удалить большую часть логики из вашего цикла.
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;
}
На каждой итерации cmpпеременная равна нулю, если два числа равны, и положительна или отрицательна в зависимости от того, было ли увеличение или уменьшение.
Когда lastCmpравно нулю, мы еще не видели увеличения или уменьшения, т.е. все целые числа были равны. Если не lastCmpравно нулю, то мы наблюдаем либо увеличение, либо уменьшение. Если последовательность не является монотонной, мы в конечном итоге достигнем пары, которая двигалась в направлении, противоположном первому изменению, что обнаружит второе условие.
Если список короче двух элементов, цикл вообще не выполняется, а просто возвращает true.
Вы можете получить более высокую производительность и простоту , если вы сделаете свой ум сразу: Сравнивая первое значение с последним значением сразу говоришь вам , который один из увеличения / уменьшения / константы вы должны проверить.
Что делать,
nullзависит от контракта. Эта проблема находится в LeetCode , где вам даже гарантируется, что в массиве будет хотя бы один элемент, поэтому вам не нужно будет покрыватьnullили пустой массив. Вы «выбрали» (?), Чтобы вернутьсяfalse, но с тем же успехом можете возразитьtrue, поскольку «без массива» кажется скорее похожим на «без элементов», для которого правильный ответ, кстатиtrue, нетfalse.
Вот тот, который использует проверку «первый vs последний» (хотя я включил «константу» в «возрастание») и которая возлагает на вызывающего пользователя бремя обеспечения разумного ввода (т. Е. Нет null). Я думаю, лучше, если пользователь получит сообщение об ошибке, чем молча делать вид, что ничего не случилось.
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;
}
BiPredicateВерсия вдохновлен ответом Rotora в . Это отличает все три случая, поскольку BiPredicateпозволяет избежать дублирования кода:
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;
}
Версия Python, просто для удовольствия :-)
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:]))
Я не большой поклонник единой монолитной функции, которая без разбора проверяет как возрастающую, так и убывающую монотонность. Я полагаю, что в большинстве практических сценариев вам, вероятно, потребуется знать, увеличивается он или уменьшается.
Исходя из этого, я бы конкретно определил:
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
}
Конечно, будет пара дублирующих проверок, но в конечном итоге, ИМО, код будет лучше структурирован, лучше читаемым и более пригодным для повторного использования.
Если принять консистенцию замечания @AJNeufeld (так что [1]быть монотонным указует , что [1,1,1]может быть довольно монотонным тоже) и поставить другое замечание о [x,y]быть монотонным снова, вы можете найти его легче иметь true-s по умолчанию и определить , когда массив не монотонный:
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;
}
Конечно, это выглядит так аккуратно только без короткого замыкания, после этого он снова будет иметь очень похожую структуру на ваш исходный код:
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;
}
Здесь я вернулся к индексированному доступу на основании моего неприятия сравнения первого элемента с самим собой (что for(:)делает вариант). Также обратите внимание, что здесь из-за короткого замыкания returnзавершение цикла означает, что массив наверняка монотонен. Кроме того, было применено замечание об опасности наличия numbers.length-1петли.