Определить локальные минимумы и максимумы, Java

Question

является любой последовательностью целых чисел, например 23 7 13 4 8 6 .Я хочу определить локальные минимумы и максимумы по следующим правилам:

• первое число в последовательности является локальным минимумом, когда следующее число больше
• последнее число в последовательностиявляется локальным минимумом, когда предыдущее число больше
• число в последовательности является локальным минимумом, когда оно меньше предыдущего, и следующее число

Я могу использовать методы hasNextInt и getNextInt .

В настоящее время я думаю об алгоритме.Но я не уверен, понимаю ли я логику.Сначала я строю кортеж и сравниваю его числа.Например, я сравниваю 23 и 7. 7 - это локальный минимум.Что бы я тогда делал?Построить тройной ?Но в каких числах эта тройка, 23 7 13 или 13 4 8?Я не уверен.

Есть идеи?

Обновление:

Допустим, мы храним левого соседа и число в середине трех чисел:

left    middle    current

0        0         23

23       0         7

23       7         13 <- you have a triple, compare => minimum 7

Что тогда будет?Установить переменные в 0 и начать со следующего числа 4?Или сохранить 7 слева, 13 посередине, чтобы иметь текущее значение 4?

Обновление (этот код работает):

    int left   = 0;
    int center = 0;
    while(hasNextInt()){
        int current = getNextInt();

        if((left != 0) && (center != 0)){
            if(current > center && center < left){
                System.out.println("Min: "+center);
                left = center; center = current;
            }else{
                left = center; center = current;
            }
        }else if((left != 0) && (center == 0)){
            if(left < current){
                System.out.println("Min: "+left);
                center = current;
            }else{
                center = current;
            }
        }else if((left == 0) && (center == 0)){
            left = current;
        }
    }

    if(left > center){
        System.out.println("Min: "+center);
    }

Спасибо за помощь!

Answer 1

Вот предложение:

private void findMin() {

    int count = 0; // To handle special case of singleton list

    int left  = Integer.MAX_VALUE;
    int mid   = Integer.MAX_VALUE;
    int right = Integer.MAX_VALUE;

    while (hasNextInt()) {
        count++;
        left = mid;
        mid = right;
        right = getNextInt();

        if (right > mid && mid < left)
            System.out.println("local min: " + mid);
    }

    if (count > 1 && right < mid)
        System.out.println("local min: " + right);
}

(доступно демо Ideone здесь .)

Answer 2

То, что у вас там, выглядит как хорошее начало.

Однако одного просмотра кортежей будет недостаточно, поскольку для определения локального минимума необходимо взглянуть на три числа, поэтому вам придется расширить свой алгоритм.

Чтобы понять, как это сделать, попробуйте создать простой пример на бумаге. Как бы вы пошли вручную найти локальные минимумы? Можете ли вы сделать что-то подобное в вашей программе?

Не стесняйтесь размещать обновленную версию вашей программы (редактируя вопрос, добавляя новый код внизу), тогда мы можем помочь, если вы все еще застряли.

Ответ на ваше редактирование:

Что тогда будет? Установить переменную до 0 и начать со следующего числа 4? Или хранить 7 слева, 13 посередине иметь 4 в качестве тока?

Вы не можете просто установить все на 0; вам все еще нужны последние два числа вашей тройки, чтобы начать следующую тройку, потому что ваши тройки ведут себя как окна, скользящие по списку чисел (это часто называют техникой «скользящего окна», так как многие алгоритмы используют ее).

Вы можете скопировать числа в их новые переменные вручную.

Для большей элегантности вы можете реализовать это в отдельном классе "Triplet". Идеи для размышления: этот класс может проверять минимумы и позволять вам добавлять новый номер, автоматически «выталкивая» самый старый номер.

Answer 3

Следуя определениям, представьте себе триплет где-то посередине последовательности:

... A, B, C,  ...

очевидно B локальных минимумов iff ( тогда и только тогда, когда ): A-B > 0 && B-C <0

в противном случае B локальные максимумы, если: A-B < 0 && B-C >0

Ничего особенного иначе

Если вы реализуете эту логику и перебираете список, специально обрабатывая случаи в конце, вы сможете найти все локальные оптимумы в O (n).

Answer 4

Отслеживайте, были ли вы ранее увеличены или уменьшены с использованием двух логических значений. Когда вы прочитаете следующее число в массиве, проверьте еще раз и сравните 4 логических значения следующим образом:

local_minimum = previously_decreased && just_increased;
local_maximum = previously_increased && just_decreased;

Затем сохраните только -> ранее и продолжайте.

В начале оба предыдущие логические значения должны быть установлены в true. В конце вам потребуется еще один проход цикла, устанавливающий оба just_ booleans в значение true.

Очевидно, что эти логические значения увеличения / уменьшения являются строгими, поэтому равные значения приведут оба логических значения как ложные.

Надеюсь, это поможет.