计算有界切片的可靠性

Question

我最近参加了编码测试的编程测试,问题是在数组中找到有界切片的数量.

我只是简单地向你解释这个问题.

如果Max(SliceArray)-Min(SliceArray)<= K,则称一个数组的切片为有界切片.

如果Array [3,5,6,7,3]和K = 2提供..有界切片的数量是9,

数组中的第一个切片(0,0)Min(0,0)= 3 Max(0,0)= 3 Max-Min <= K结果0 <= 2因此它是有界切片

数组中的第二个切片(0,1)Min(0,1)= 3 Max(0,1)= 5 Max-Min <= K结果2 <= 2所以它是有界切片

数组中的第二个切片(0,2)Min(0,1)= 3 Max(0,2)= 6 Max-Min <= K结果3 <= 2因此它不是有界切片

通过这种方式你可以发现有九个有界切片.

(0,0),(0,1),(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4) ,4).

以下是我提供的解决方案

private int FindBoundSlice(int K, int[] A)
{
    int BoundSlice=0;
    Stack<int> MinStack = new Stack<int>();
    Stack<int> MaxStack = new Stack<int>();




    for (int p = 0; p < A.Length; p++)
    {
        MinStack.Push(A[p]);
        MaxStack.Push(A[p]);
        for (int q = p; q < A.Length; q++)
        {
            if (IsPairBoundedSlice(K, A[p], A[q], MinStack, MaxStack))
                BoundSlice++;
            else
                break;
        }
    }

    return BoundSlice;
}

private bool IsPairBoundedSlice(int K, int P, int Q,Stack<int> Min,Stack<int> Max)
{
    if (Min.Peek() > P)
    {
        Min.Pop();
        Min.Push(P);
    }

    if (Min.Peek() > Q)
    {
        Min.Pop();
        Min.Push(Q);
    }

    if (Max.Peek() < P)
    {
        Max.Pop();
        Max.Push(P);
    }

    if (Max.Peek() < Q)
    {
        Max.Pop();
        Max.Push(Q);
    }

    if (Max.Peek() - Min.Peek() <= K)
        return true;
    else
        return false;
}

但是根据能力审查,上面提到的解决方案是在O(N ^ 2)中运行,任何人都可以帮助我找到在O(N)中运行的解决方案.

最大时间复杂度允许O(N).最大空间复杂度允许O(N).

Answer 1

提示

其他人已经解释了基本算法，即保留 2 个指针并根据当前最大值和最小值之间的差异提前开始或结束。

移动末端时很容易更新最大值和最小值。

然而，这个问题的主要挑战是移动启动时如何更新。大多数堆或平衡树结构的更新成本为 O(logn)，并且会导致总体 O(nlogn) 复杂度过高。

要在 O(n) 时间内完成此操作：

1. 提前结束，直到超过允许的阈值
2. 然后从这个关键位置向后循环，在数组中存储当前结束和当前开始之间每个位置的最小值和最大值的累积值
3. 您现在可以前进开始指针并立即从数组中查找更新的最小/最大值
4. 您可以继续使用这些数组来更新 start ，直到 start 到达临界位置。此时返回步骤 1 并生成一组新的查找值。

总的来说，这个过程将在每个元素上向后运行一次，因此总复杂度为 O(n)。

例子

对于 K 为 4 的序列：

4,1,2,3,4,5,6,10,12

第 1 步推进结束，直到超出界限

start,4,1,2,3,4,5,end,6,10,12

第 2 步从头开始向后计算数组 MAX 和 MIN。MAX[i] 是从 i 到 end 的所有元素中的最大值

Data = start,4,1,2,3,4,5,end,6,10,12
MAX  = start,5,5,5,5,5,5,critical point=end -
MIN  = start,1,1,2,3,4,5,critical point=end -

步骤 3 现在可以提前开始并立即查找开始到临界点范围内的 max 和 min 的最小值。

这些可以与临界点到结束范围内的最大/最小值相结合，以找到从开始到结束的范围的总体最大/最小值。

Python代码

4,1,2,3,4,5,6,10,12