计数有界切片密码
我最近参加了一个密码编程测试，问题是如何在数组中找到有界切片的数目。
我只是简单地解释一下这个问题。
如果Max(SliceArray)-Min(SliceArray)<=K，则表示数组的一个切片是有界的。
如果数组3,5,6,7,3和K=2提供。有界切片的数目是9，
数组中的第一片(0,0) =3 Max(0,0)=3 Max-Min<=K结果0<=2，因此它是有界切片
数组中的第二片(0,1) =3 Max(0,1)=5 Max-Min<=K结果2<=2，因此它是有界切片
数组Min(0,1)=3 Max (0,2) =6 Max-Min<=K结果3<=2中的第二片(0，2)，因此它不是有界切片
通过这种方式，您可以发现有九个有界的切片。
(0，0)，(0，1)，(1，1)，(1，2)，(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)。
回答 6
Stack Overflow用户
发布于 2014-01-21 02:12:31
提示
其他人解释了基本算法，即根据最大和最小之间的当前差值，保持2个指针并提前开始或结束。
移动结束时很容易更新最大值和最小值。
然而，这个问题的主要挑战是如何在移动开始时进行更新。大多数堆或平衡的树结构将花费O(logn)更新，并将导致整体O(nlogn)复杂性过高。
为及时做到这一点，O(n)：
- 提前结束直到超过允许的阈值。
- 然后从这个关键位置向后循环，在数组中存储一个累积值，以便在当前结束和当前启动之间的每个位置上达到最小值和最大值。
- 现在，您可以从更新的min/max值的数组中提升开始指针并立即查找。
- 您可以继续使用这些数组来更新start，直到start达到临界位置。此时返回到步骤1，并生成一组新的查找值。
总的来说，这个过程只对每个元素进行一次反向工作，所以总复杂度是O(n)。
示例
对于K为4的序列：
4,1,2,3,4,5,6,10,12第一步向前推进，直到我们超过界限。
start,4,1,2,3,4,5,end,6,10,12步骤2从端到端向后工作，计算数组MAX和MIN。MAXi是从i到结束的所有元素的最大值。
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现在可以提前、启动并立即查找范围内最小的最大值和最小值，开始到临界点。
这些可以与范围临界点到终点的最大/分钟相结合，以找到范围开始到结束的总体最大/分钟。
PYTHON代码
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)Stack Overflow用户
发布于 2015-10-26 14:20:57
现在，仁慈释放他们的黄金解与O(N)的时间和空间。https://codility.com/media/train/solution-count-bounded-slices.pdf
如果你看完pdf后还很困惑，就像我一样.这是一个很好的解释
pdf中的解决方案：
def boundedSlicesGolden(K, A):
N = len(A)
maxQ = [0] * (N + 1)
posmaxQ = [0] * (N + 1)
minQ = [0] * (N + 1)
posminQ = [0] * (N + 1)
firstMax, lastMax = 0, -1
firstMin, lastMin = 0, -1
j, result = 0, 0
for i in xrange(N):
while (j < N):
# added new maximum element
while (lastMax >= firstMax and maxQ[lastMax] <= A[j]):
lastMax -= 1
lastMax += 1
maxQ[lastMax] = A[j]
posmaxQ[lastMax] = j
# added new minimum element
while (lastMin >= firstMin and minQ[lastMin] >= A[j]):
lastMin -= 1
lastMin += 1
minQ[lastMin] = A[j]
posminQ[lastMin] = j
if (maxQ[firstMax] - minQ[firstMin] <= K):
j += 1
else:
break
result += (j - i)
if result >= maxINT:
return maxINT
if posminQ[firstMin] == i:
firstMin += 1
if posmaxQ[firstMax] == i:
firstMax += 1
return resultStack Overflow用户
发布于 2014-01-21 01:56:13
以下是我解决这个问题的尝试：
- you start with p and q form position 0, min =max =0;
- loop until p = q = N-1
- as long as max-min<=k advance q and increment number of bounded slides.
- if max-min >k advance p
- you need to keep track of 2x min/max values because when you advance p, you might remove one or both of the min/max values
- each time you advance p or q update min/max如果你想的话，我可以写代码，但我认为这个想法很明确.
希望能帮上忙。
https://stackoverflow.com/questions/21251707
复制
腾讯云开发者
