算法题: Largest contiguous subarray selection

Question

问。给定两个长度相等的数组 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) 蛮力方法中做到这一点，但似乎无法降低时间复杂度。有什么想法吗？

Answer 1

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}')