检测局部最小值和最大值，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);
    }

感谢您的帮助！

- DarkLeafyGreen

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

- aioobe

---

谢谢你的代码。但是为什么要使用Integer.MAX_VALUE而不是0？ - DarkLeafyGreen

Answer 2

你所拥有的看起来是一个不错的开端。

然而，仅仅查看元组是不够的，因为你必须查看三个数字才能检测到局部最小值——因此你需要扩展你的算法。

要理解如何做到这一点，请尝试在纸上处理一个简单的例子。你会如何手动找到局部最小值？你能在程序中做类似的事情吗？

如果你还卡住了，可以随意发布更新后的程序版本（通过编辑问题，在底部添加新代码），然后我们可以帮助你。

回答你的编辑：

那么会发生什么呢？将变量设置为0，然后从下一个数字4开始吗？或者将7存储在左侧，将13存储在中间，以便将4作为当前值？

你不能只将所有内容都设置为0；你仍然需要将你的三元组的最后两个数字用于启动下一个三元组，因为你的三元组就像一个窗口滑过数字列表一样（这通常被称为“滑动窗口”技术，因为许多算法使用它）。

你可以手动复制数字到它们的新变量中。

为了更加优雅，你可以在一个单独的“Triplet”类中实现这个功能。需要考虑的想法：该类可以检查最小值，并让你添加一个新的数字，自动“推出”最旧的数字。

- sleske

---

谢谢你提供的滑动三元组想法，非常有帮助！我已经更新了我的代码。 - DarkLeafyGreen

Answer 3

使用两个布尔值来跟踪您以前是否增加或减少。当您读取数组中的下一个数字时，请再次检查并比较这4个布尔值：

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

然后仅存储 -> 以前并继续。

一开始，两个 previous_ 布尔值都应该设置为 true。最后，您需要另一个循环通过将两个 just_ 布尔值设置为 true。

显然，这些增加/减少布尔值是严格的，因此相等的值将使两个布尔值为 false。

希望这有所帮助。

- Dijkstra

Answer 4

根据定义，在序列的中间考虑一个三元组：

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

显然B局部最小值当且仅当 ( if and only if ）：A-B > 0 && B-C <0

否则，B的局部最大值当且仅当： A-B < 0 && B-C > 0

否则没有特别情况

如果您实现此逻辑，并迭代列表，特别处理末尾的情况，则应该能够在O（n）中找到所有局部最优解。

- posdef