Detect local minima and maxima, java

Question

given is any sequence of integers like 23 7 13 4 8 6. I want to detect local minima and maxima with the following rules:

• the first number in the sequence is a local minimum when the following number is greater
• the last number in the sequence is a local minimum when the previous number is greater
• a number in the sequence is a local minimum when it is smaller than the previous and the following number

I can use the methods hasNextInt and getNextInt.

Currently I am thinking about the algorithm. But I am not sure whether I understand the logic. First I build a tuple and compare its numbers. E.g. I compare 23 and 7. 7 is the local minimum. What would I do then? Build a triple? But what numbers has that triple, 23 7 13 or 13 4 8? I am not sure.

Any ideas?

Update:

Let's say we store the left neighbour and the number in the middle of three numbers:

left    middle    current

0        0         23

23       0         7

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

What would happen then? Set the vars to 0 and start with the next number 4? Or store 7 in left, 13 in the middle to have 4 as current?

Update (this code seems to work):

    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);
    }

Thanks for your help!

Answer 1

Here is a suggestion:

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);
}