问。给定两个长度相等的数组 A 和 B,找到索引 [i,j] 的最大可能连续子数组,使得 max(A[i: j]) < min(B[i: j]).
例子:A = [10, 21, 5, 1, 3], B = [3, 1, 4, 23, 56]
解释:A[4] = 1, A[5] = 3, B[4] = 23, B[5] = 56, max(A[4], A[5]) < min(B[ 4], B[5])
索引为[4,5](含),最大的连续子数组长度为2
我可以在 O(n2) 蛮力方法中做到这一点,但似乎无法降低时间复杂度。有什么想法吗?
最佳答案
O(n) 解:
从左向右移动索引 j
并将 i
拖到后面,以便窗口从 i
到 j
已验证。因此,总是将 j
加 1,然后根据需要增加 i
以使窗口有效。
要做到这一点,请保留一个队列 Aq
,其中包含非递增 A 值的索引。然后 A[Aq[0]]
告诉您窗口中的最大 A 值。同样,为非递减 B 值保留一个队列。
对于每一个新的j
,首先根据新的A值和新的B值更新Aq
和Bq
。然后,当窗口无效时,增加 i
并删除 Aq[0]
和 Bq[0]
如果它们是 i
。当 j
和 i
都更新时,将结果更新为窗口大小 j - i - 1
。
Python 实现:
def solution(A, B):
Aq = deque()
Bq = deque()
i = 0
maxlen = 0
for j in range(len(A)):
while Aq and A[Aq[-1]] < A[j]:
Aq.pop()
Aq.append(j)
while Bq and B[Bq[-1]] > B[j]:
Bq.pop()
Bq.append(j)
while Aq and A[Aq[0]] >= B[Bq[0]]:
if Aq[0] == i:
Aq.popleft()
if Bq[0] == i:
Bq.popleft()
i += 1
maxlen = max(maxlen, j - i + 1)
return maxlen
与原始暴力引用解决方案进行比较的测试结果:
expect: 83 result: 83 same: True
expect: 147 result: 147 same: True
expect: 105 result: 105 same: True
expect: 71 result: 71 same: True
expect: 110 result: 110 same: True
expect: 56 result: 56 same: True
expect: 140 result: 140 same: True
expect: 109 result: 109 same: True
expect: 86 result: 86 same: True
expect: 166 result: 166 same: True
测试代码(Try it online!)
from timeit import timeit
from random import choices
from collections import deque
from itertools import combinations
def solution(A, B):
Aq = deque()
Bq = deque()
i = 0
maxlen = 0
for j in range(len(A)):
while Aq and A[Aq[-1]] < A[j]:
Aq.pop()
Aq.append(j)
while Bq and B[Bq[-1]] > B[j]:
Bq.pop()
Bq.append(j)
while Aq and A[Aq[0]] >= B[Bq[0]]:
if Aq[0] == i:
Aq.popleft()
if Bq[0] == i:
Bq.popleft()
i += 1
maxlen = max(maxlen, j - i + 1)
return maxlen
def naive(A, B):
return max((j - i + 1
for i, j in combinations(range(len(A)), 2)
if max(A[i:j+1]) < min(B[i:j+1])),
default=0)
for _ in range(10):
n = 500
A = choices(range(42), k=n)
B = choices(range(1234), k=n)
expect = naive(A, B)
result = solution(A, B)
print(f'expect: {expect:3} result: {result:3} same: {result == expect}')
关于算法题: Largest contiguous subarray selection,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69180529/