我最近参加了codility编程测试，问题是要找到有界片的数量在数组中。

I have recently attended a programming test in codility, and the question is to find the Number of bounded slice in an array..

我只是给你breif问题的解释。

I am just giving you breif explanation of the question.

数组切片说是一个有界一片，如果马克斯（SliceArray）-Min（SliceArray）＆LT; = K

A Slice of an array said to be a Bounded slice if Max(SliceArray)-Min(SliceArray)<=K.

如果数组[3,5,6,7,3]和K = 2提供..界片的数目为9，

If Array [3,5,6,7,3] and K=2 provided .. the number of bounded slice is 9,

第一片（0,0）的阵列最小（0,0）= 3最大（0,0）= 3的Max-分钟＆lt在; = K结果0℃= 2所以它是有界的片

first slice (0,0) in the array Min(0,0)=3 Max(0,0)=3 Max-Min<=K result 0<=2 so it is bounded slice

第二片（0,1）的阵列敏（0,1）= 3 MAX（0,1）= 5最大，最小和LT在; = K结果2'= 2那么它是有界的片

second slice (0,1) in the array Min(0,1)=3 Max(0,1)=5 Max-Min<=K result 2<=2 so it is bounded slice

第二切片（0,2）的阵列最小（0,1）= 3最大（0,2）= 6的Max-分钟＆lt在; = K结果3'= 2，因此是无界片

second slice (0,2) in the array Min(0,1)=3 Max(0,2)=6 Max-Min<=K result 3<=2 so it is not bounded slice

在这种方式，你可以发现，有九界片。

in this way you can find that there are nine bounded slice.

（0,0），（0,1），（1,1），（1,2），（1,3），（2,2），（2,3），（3，3） ，（4，4）。

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

以下是我所提供的解决方案

Following is the solution i have provided

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

不过，按照codility审查上述解决办法是O（N ^ 2）运行时，任何人可以帮助我找到它运行在O（N）的解决方案。

But as per codility review the above mentioned solution is running in O(N^2), can anybody help me in finding the solution which runs in O(N).

最大时间复杂度允许的O（N）。 最大空间复杂度允许的O（N）。

Maximum Time Complexity allowed O(N). Maximum Space Complexity allowed O(N).

推荐答案

其他人已经解释的基本算法是保持2指针和推进的开始或结束时根据最大和最小之间的电流差。

HINTS

Others have explained the basic algorithm which is to keep 2 pointers and advance the start or the end depending on the current difference between maximum and minimum.

有容易更新的最大值和最小值时移动所述端

It is easy to update the maximum and minimum when moving the end.

不过，这个问题的主要挑战是如何在移动开始更新。大多数堆或平衡树结构将花费O（LOGN）进行更新，并会导致整体O（nlogn）的复杂性是太高了。

However, the main challenge of this problem is how to update when moving the start. Most heap or balanced tree structures will cost O(logn) to update, and will result in an overall O(nlogn) complexity which is too high.

要做到这一点的时间为O（n）：

To do this in time O(n):

总之这个过程可以通过向后每个元素恰好一次，所以总的复杂度为O（n）。

Overall this procedure will work backwards over every element exactly once, and so the total complexity is O(n).

对于4K的顺序：

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

第1步前进到底，直到我们超越边界

Step 1 advances the end until we exceed the bound

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

步骤2向后工作从年底开始计算阵列MAX和MIN。 MAX [i]为最大的所有元素，从我结束

Step 2 works backwards from end to start computing array MAX and MIN. MAX[i] is maximum of all elements from i to 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现在可以提前启动，并立即查找范围内开始到临界点的最大和最小的最小值。

Step 3 can now advance start and immediately lookup the smallest values of max and min in the range start to critical point.

这些可以用最大合并/分范围内的临界点结束，找到整体的最大/最小的范围内开始到结束。

These can be combined with the max/min in the range critical point to end to find the overall max/min for the range start to end.

def count_bounded_slices(A,k):
    if len(A)==0:
        return 0
    t=0
    inf = max(abs(a) for a in A)
    left=0
    right=0
    left_lows = [inf]*len(A)
    left_highs = [-inf]*len(A)
    critical = 0
    right_low = inf
    right_high = -inf
    # Loop invariant
    #  t counts number of bounded slices A[a:b] with a<left
    #  left_lows[i] is defined for values in range(left,critical)
    #    and contains the min of A[left:critical]
    #  left_highs[i] contains the max of A[left:critical]
    #  right_low is the minimum of A[critical:right]
    #  right_high is the maximum of A[critical:right]
    while left<len(A):
        # Extend right as far as possible
        while right<len(A) and max(left_highs[left],max(right_high,A[right]))-min(left_lows[left],min(right_low,A[right]))<=k:
            right_low = min(right_low,A[right])
            right_high = max(right_high,A[right])
            right+=1    
        # Now we know that any slice starting at left and ending before right will satisfy the constraints
        t += right-left
        # If we are at the critical position we need to extend our left arrays
        if left==critical:
            critical=right
            left_low = inf
            left_high = -inf
            for x in range(critical-1,left,-1):
                left_low = min(left_low,A[x])
                left_high = max(left_high,A[x])
                left_lows[x] = left_low
                left_highs[x] = left_high
            right_low = inf
            right_high = -inf
        left+=1
    return t

A = [3,5,6,7,3]
print count_bounded_slices(A,2)