Выяснение увеличения или уменьшения монотонного массива в java

Это вопрос интервью.

Узнайте, является ли входной массив метода возрастающим или убывающим. Галстуки будут идти в соответствии с текущим порядком. Я имею в виду, если другие члены увеличиваются, а некоторые из них или равны его штрафу, и то же самое верно для убывающих элементов. Функция возвращает истину или ложь.

Я сделал это таким образом. Я думаю, есть ли другой, но творческий способ сделать это.

boolean isMonotonic(int[] arr){
    if(arr.length <= 2){
        return true;
    }
    boolean increasing = true;
    boolean decreasing = true;
    for (int i=1; i<arr.length; i++){
        if (arr[i-1] > arr[i]){
            increasing = false;
        } else if(arr[i-1] < arr[i]){
            decreasing = false;
        }
        if (!increasing && !decreasing){
            return false;
        }
    }
    return true;
}

java arrays sortedlist
person Sahib Khan    schedule 01.10.2017    source источник
comment
Ваше решение чистое, делает всего один проход по массиву, и я не уверен, что это можно сделать более элегантно. Другой способ сформулировать, что увеличение haa переключилось на уменьшение, состоит в том, чтобы отслеживать предыдущий и предпоследний ходы.   -  person Tim Biegeleisen    schedule 01.10.2017

Ответы (2)


arrow_upward
3
arrow_downward

Ваше решение очень хорошее, быстрое и эффективное.

Важно то, что вы зацикливаете массив только один раз, поэтому ваша сложность линейна O(n), и нет более эффективного решения, чем это. Тем не менее, необходимо немного изменить его, чтобы заставить его работать. Всякий раз, когда вы умножаете на 0, как вы это делаете, ответ всегда равен 0. Поэтому вы должны изменить инициализацию на = 1, а не на 0.

Да, вы можете использовать коллекции, которые предлагает Java, чтобы сохранить больше строк или сделать его немного более читабельным, но зачем? Лично я думаю, что вы предоставили чистое решение этой проблемы, и нет причин рефакторить решение, если оно умное, простое и эффективное. :)

person Nikolas Charalambidis    schedule 01.10.2017

arrow_upward
0
arrow_downward

Я не уверен, что это будет более эффективно. Но мы можем вычислить разницу между соседними элементами. Если дифф постоянно отрицательный или 0 - последовательность убывающая. Если он положительный или 0 - увеличивается. Мы должны обнаружить точку, в которой diff меняет свой знак. Чтобы избежать операторов «если», мы можем использовать умножение. В монотонной последовательности умножение двух дифференциалов всегда будет положительным или равным 0.

static boolean isMonotonic(int[] arr){
    if(arr.length <= 2){
        return true;
    }
    int diff = 0;
    for (int i=1; i<arr.length; i++){
        int newDiff = arr[i] - arr[i-1];
        if (newDiff * diff < 0) {
            return false;
        }
        diff = newDiff;
    }
    return true;
}
person Azee    schedule 17.01.2019
comment
Вы правы, но решение все равно будет O(n), поэтому я думаю, что оно похоже. - person Sahib Khan; 17.01.2019