数组平衡点

Question

解决这个问题的最好方法是什么？N元数组A的平衡点是索引i，使得较低索引上的所有元素具有值<= Ai，而较高索引上的所有元素具有大于或等于Ai的值。

例如，给定：

A=4 A1=2 A2=7 A3=11 A4=9

正确的解决方案之一是: 2. A2以下的所有元素都小于A2，A2之后的所有元素都大于A2。出现在我脑海中的一个解决方案是O(nsquare)解决方案。有没有更好的解决方案？

Answer 1

首先假设A[0]是一根杆子。然后开始遍历数组；将每个元素A[i]依次与A[0]进行比较，并跟踪当前的最大值。

一旦找到A[i] < A[0]这样的i，就会知道A[0]不能再是一个极点，延伸到A[i]之前的任何元素也不能。所以现在继续遍历，直到找到下一个大于当前最大值的值。然后，这将成为新提议的极点。

因此，一个O(n)解！

在代码中：

int i_pole = 0;
int i_max  = 0;
bool have_pole = true;
for (int i = 1; i < N; i++)
{
    if (A[i] < A[i_pole])
    {
        have_pole = false;
    }
    if (A[i] > A[i_max])
    {
        i_max = i;
        if (!have_pole)
        {
            i_pole = i;
        }
        have_pole = true;
    }
}

Answer 2

如果您想知道所有极点的位置，O(n log n)解决方案将是创建数组的排序副本，并查看从何处获得匹配值。

编辑:很抱歉，但这实际上不起作用。一个反例是[2, 5, 3, 1, 4]。

Answer 3

创建两个辅助数组，每个辅助数组的元素数量与输入数组相同，分别称为MIN和MAX。MAX的每个元素M包含来自0..M的输入中的所有元素的最大值。MIN的每个元素M包含来自M..N-1的输入中的所有元素的最小值。

对于输入数组的每个元素M，将其值与MIN和MAX中的相应值进行比较。如果INPUTM == MINM和INPUTM == MAXM，则M是一个平衡点。

构建MIN需要N个步骤，MAX也是如此。然后再执行N个步骤来测试阵列。这个解决方案的复杂度为O(N)，并且找到了所有的平衡点。在排序输入的情况下，每个元素都是一个平衡点。