java - 在一维数组/直方图中查找局部最小值/最大值

我试图找到数组中所有局部最小值和最大值的索引。

例子:

int[] array = {5,4,3,3,3,3,3,2,2,2,  6,6,8,5,5,5,3,3,2,1,  1,4,4,7};
//                             |         |                 |
// Indices:    0,1,2,3,4,5,6,7,8,9, 10,1,2,3,4,5,6,7,8,9, 20,1,2,3
// Minima: 8, 20
// Maxima: 12

我想出了一个算法，对此我有几个问题:

有更好的吗？ :)

我使用了一个带有方法的 Enum 来实现这种二元论，即 UP 和 STRAIGHT_UP 都是“UP”。对我来说似乎很乱。有什么建议么？

你有更好的方法名吗？ direction() (+return value) 有点暗示 STRAIGHT 不是目录。但同时它也是，因为它是 Emum 中的一个元素。嗯。

它适用于给定的数组。你看到没有的情况吗？

——

import java.util.ArrayList;


public class MinMaxFinder {
    private int[] array;
    private ArrayList<Integer> minima;
    private ArrayList<Integer> maxima;


    private enum Direction{
        UP, DOWN, STRAIGHT_UP, STRAIGHT_DOWN, STRAIGHT;

        public Direction direction(){
            if(this==UP || this==STRAIGHT_UP){
                return UP;
            }else if(this==DOWN || this==STRAIGHT_DOWN){
                return DOWN;
            }else{
                return STRAIGHT;
            }
        }

        public boolean isStraight(){
            if(this==STRAIGHT_DOWN || this==STRAIGHT_UP || this==STRAIGHT){
                return true;
            }else{
                return false;
            }
        }

        public boolean hasDifferentDirection(Direction other){
            if(this!=STRAIGHT && other!=STRAIGHT && this.direction() != other.direction() ){
                return true;
            }
            return false;
        }
    }

    public MinMaxFinder(int[] array){
        this.array = array;
    }

    public void update() {
        minima = new ArrayList<Integer>();
        maxima = new ArrayList<Integer>();

        Direction segmentDir = Direction.DOWN;
        int indexOfDirectionChange = 0;
        int prevVal = array[0];
        int arrayLength = array.length;
        for(int i=1; i<arrayLength; i++){
            int currVal = array[i];
            Direction currentDir = currVal<prevVal?Direction.DOWN:(currVal>prevVal?Direction.UP:Direction.STRAIGHT);
            prevVal = currVal;

            if(currentDir.hasDifferentDirection(segmentDir)){
                int changePos = (indexOfDirectionChange+i-1)/2;
                if(currentDir.direction() == Direction.DOWN){
                    maxima.add(changePos);
                }else{
                    minima.add(changePos);
                }

                segmentDir = currentDir;
                indexOfDirectionChange = i;
            }else if( currentDir.isStraight() ^ segmentDir.isStraight() ){
                indexOfDirectionChange = i;

                if(currentDir.isStraight() && segmentDir.direction()==Direction.UP){
                    segmentDir=Direction.STRAIGHT_UP;
                }else if(currentDir.isStraight() && segmentDir.direction()==Direction.DOWN){
                    segmentDir=Direction.STRAIGHT_DOWN;
                }else{
                    segmentDir = currentDir;
                }
            }
        }
    }

    public ArrayList<Integer> getMinima() {
        return minima;
    }

    public ArrayList<Integer> getMaxima() {
        return maxima;
    }
}

最佳答案

考虑一阶差分数组 d[i] = a[i] - a[i-1] 。

如果 d[i] 为正，则 a 在最后一步增加，如果 d[i] 为负，则 a 减少。因此，d 的符号从正变为负表示 a 正在增加，现在正在减少，达到局部最大值。类似地，从负到正表示局部最小值。

关于java - 在一维数组/直方图中查找局部最小值/最大值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13157510/