c# - 在具有非不同元素的数组中查找局部最小值

Question

输入数组类似于:

[0,0,1,2,4,7,9,6,4,4,2,1,0,0,0,0,0,3,5,5,10,3,2,1,4,5,7,7,12,11,8,4,2,
 1,1,1,2,4,9,4,2,2,0,1,3,6,13,11,5,5,2,2,3,4,7,11,8...]

正如我们所看到的，数组中有山丘和山谷，同一山谷具有重复的(可能)最小值。我扩展了This (地址具有不同元素的数组)找到上述解决方案的想法为:

/// <summary>
/// Returns index array where valley lies
/// </summary>
/// <param name="arraySmoothed"></param>
/// <returns></returns>
private static List<int> GetValleys(List<int> arraySmoothed) {
    List<int> valleys = new List<int>();
    List<int> tempValley = new List<int>();

    bool contdValleyValues = false;
    for (int i = 0; i < arraySmoothed.Count; i++) {
        // A[i] is minima if A[i-1] >= A[i] <= A[i+1], <= instead of < is deliberate otherwise it won't work for consecutive repeating minima values for a valley
        bool isValley = ((i == 0 ? -1 : arraySmoothed[i - 1]) >= arraySmoothed[i]) 
            && (arraySmoothed[i] <= (i == arraySmoothed.Count - 1 ? -1 : arraySmoothed[i + 1]));

        // If several equal minima values for same valley, average the indexes keeping in temp list
        if (isValley) {
            if (!contdValleyValues)
                contdValleyValues = true;
            tempValley.Add(i);
        } else  {
            if (contdValleyValues) {
                valleys.Add((int)tempValley.Average());
                tempValley.Clear();
                contdValleyValues = false;
            }
        }
    }
    return valleys;
}

此方法卡在 ...7,9,6,4,4,2,1,0,0,0,0,0,3,5,5,10,3... 抛出三个最小值，但应该有一个(五个中间的0)。复杂性对我来说不是问题，会崇拜 O(n) .我只想要一个通用的解决方案。任何提示/帮助将不胜感激。

Answer 1

您可以使用一个简单的状态机对此进行编码，该状态机具有代表曲线最近历史的三个状态:

往下走

下跌后等幅

不跌(即涨后平)

状态转换图如下所示:



图片看起来有点复杂，但描述很简单:
- 当曲线向上倾斜时，下一个状态是NotGoingDown- 当曲线向下倾斜时，下一个状态是GoingDown- 当拉伸(stretch)为水平时，状态变为EqGoingDown如果曲线下降，或NotGoingDown曲线是平坦的还是上升的。

这是 C# 中的一个实现:

enum CurveState {
    GoingDown=0, EqGoingDown=1, NotGoingDown=2
}
private static IList<int> GetValleys(IList<int> a) {
    var res = new List<int>();
    if (a.Count < 2) {
        return res;
    }
    int lastEq = 0;
    CurveState s = CurveState.NotGoingDown;
    for (var i = 1 ; i != a.Count ; i++) {
        switch(Math.Sign(a[i]-a[i-1])) {
            case -1:
                s = CurveState.GoingDown;
                break;
            case  0:
                if (s == CurveState.GoingDown) {
                    lastEq = i;
                }
                s = (s==CurveState.NotGoingDown)
                  ? CurveState.NotGoingDown
                  : CurveState.EqGoingDown;
                break;
            case 1:
                if (s == CurveState.GoingDown) {
                    res.Add(i-1);
                } else if (s == CurveState.EqGoingDown) {
                    res.Add((lastEq+i-1)/2);
                }
                s = CurveState.NotGoingDown;
            break;
        }
    }
    return res;
}

Demo使用你的数字，用星号标记山谷。
lastEq变量是当前相等范围开始的位置的索引。请注意，转换表的设置方式为 lastEq当我们在 CurveState.EqGoingDown 中时总是设置状态。 (lastEq+i-1)/2公式计算值相等的最后一个位置与 i-1 之间的平均值。 .