算法问题：最大连续子数组选择

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],乙[5])

索引为 [4,5]（含），最大连续子数组的长度为 2

我可以用 O(n2) 蛮力方法做到这一点，但似乎无法降低时间复杂度。有任何想法吗？

Answer 1

O(n) 解：

\n

将索引j从左向右移动并向后拖动，使从到 的i窗口有效。因此，始终增加1，然后根据窗口有效所需的数量增加。ijji

\n

为此，请保留一个Aq不增加 A 值的索引队列。然后A[Aq[0]]告诉您窗口中的最大 A 值。同样，为不递减的 B 值保留一个队列。

\n

对于每个新的j，首先根据新的 A 值和新的 B 值更新Aq和。Bq然后，当窗口无效时，增加i和减少Aq[0]，Bq[0]如果它们是i。当 和j都i更新时，用窗口大小 更新结果j - i - 1。

\n

Python实现：

\n

def solution(A, B):\n    Aq = deque()\n    Bq = deque()\n    i = 0\n    maxlen = 0\n    for j in range(len(A)):\n        while Aq and A[Aq[-1]] < A[j]:\n            Aq.pop()\n        Aq.append(j)\n        while Bq and B[Bq[-1]] > B[j]:\n            Bq.pop()\n        Bq.append(j)\n        while Aq and A[Aq[0]] >= B[Bq[0]]:\n            if Aq[0] == i:\n                Aq.popleft()\n            if Bq[0] == i:\n                Bq.popleft()\n            i += 1\n        maxlen = max(maxlen, j - i + 1)\n    return maxlen\n

\n

与简单的暴力参考解决方案进行比较的测试结果：

\n

expect:  83   result:  83   same: True\nexpect: 147   result: 147   same: True\nexpect: 105   result: 105   same: True\nexpect:  71   result:  71   same: True\nexpect: 110   result: 110   same: True\nexpect:  56   result:  56   same: True\nexpect: 140   result: 140   same: True\nexpect: 109   result: 109   same: True\nexpect:  86   result:  86   same: True\nexpect: 166   result: 166   same: True\n

\n

测试代码（在线尝试！）

\n

from timeit import timeit\nfrom random import choices\nfrom collections import deque\nfrom itertools import combinations\n\ndef solution(A, B):\n    Aq = deque()\n    Bq = deque()\n    i = 0\n    maxlen = 0\n    for j in range(len(A)):\n        while Aq and A[Aq[-1]] < A[j]:\n            Aq.pop()\n        Aq.append(j)\n        while Bq and B[Bq[-1]] > B[j]:\n            Bq.pop()\n        Bq.append(j)\n        while Aq and A[Aq[0]] >= B[Bq[0]]:\n            if Aq[0] == i:\n                Aq.popleft()\n            if Bq[0] == i:\n                Bq.popleft()\n            i += 1\n        maxlen = max(maxlen, j - i + 1)\n    return maxlen\n\ndef naive(A, B):\n    return max((j - i + 1\n                for i, j in combinations(range(len(A)), 2)\n                if max(A[i:j+1]) < min(B[i:j+1])),\n               default=0)\n\nfor _ in range(10):\n    n = 500\n    A = choices(range(42), k=n)\n    B = choices(range(1234), k=n)\n    expect = naive(A, B)\n    result = solution(A, B)\n    print(f\'expect: {expect:3}   result: {result:3}   same: {result == expect}\')\n

\n