演算法問題。最大的連續子陣列選擇

Q. 給定兩個等長的陣列A和B，請找出索引[i,j]的最大可能的連續子陣列，使得max(A[i: j]) < min(B[i: j])。

舉例說明。A = [10, 21, 5, 1, 3], B = [3, 1, 4, 23, 56]/p>

解釋一下。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)的蠻力方法做到這一點，但似乎不能減少時間的復雜性。有什么想法嗎？

uj5u.com熱心網友回復：

O(n)解決方案：

從左到右移動索引j，并將i拖在后面，這樣從i到j的視窗就會有效。因此，總是將j增加1，然后根據需要增加i，以使視窗有效。

要做到這一點，請保留一個非遞增A值的索引佇列Aq。然后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]] 。
            如果Aq[0] == i:
                Aq.popleft()
            如果Bq[0] == i:
                Bq.popleft()
            i  = 1
        maxlen = max(maxlen, j - i   1)
    回傳maxlen

與一個天真的蠻力參考方案進行比較的測驗結果：

測驗代碼（在線試用！)

from timeit import timeit
from random import choices
從collection匯入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]] 。
            如果Aq[0] == i:
                Aq.popleft()
            如果Bq[0] == i:
                Bq.popleft()
            i  = 1
        maxlen = max(maxlen, j - i   1)
    回傳maxlen

def naive(A, B):
    回傳max((j - i   1
                for i, j in combinations(range(len(A)), 2)
                if max(A[i:j 1]) < min(B[i:j 1])) 。
               默認=0)

for _ in range(10):
    n = 500
    A = choices(range(42), k=n)
    B = choices(range(1234), k=n)
    expect = naive(A, B)
    結果 = 解決方案(A, B)
    print(f'expect: {expect:3} result: {result:3} same: {result == expect}' )

uj5u.com熱心網友回復：

我可以看到根據問題，說我們有2個條件：

• max(A[i,j-1]) < min(B[i,j-1])
• max(A[i,j]) >=min(B[i,j])
• 表示maxA是A陣列中[i,j]的最大項的索引，minB是B陣列中[i,j]的最小項的索引；而anchor是min(maxA, minB)

那么我們將得到：max(A[i k,anchor]) >= min(B[i k,anchor])? k在[i 1,anchor]。

所以我想出了一個簡單的演算法，如下所示：

使用這種方法，其復雜度為O(n)。 如果需要的話，我們可以改變輸出以獲取其他資訊。

uj5u.com熱心網友回復：

這可以在O(n log(n))中得到解決。

下面是我的技術概要。

我的想法看起來就像在A中最大的 "水位上升"，跟蹤A中出現的 "島嶼"，以及B中淹沒的 "島嶼"。并記錄從A出現后，或從B沉沒前的最大交叉點。

我們將需要在A和B中的2個平衡的二進制樹的間隔，以及一個事件的優先佇列。

區間樹需要支持對數的 "尋找并回傳包含i的區間（如果它存在）"。 它還需要支持對數的 "將i添加到樹中，適當地擴展/合并區間，并回傳新的區間"。 同樣，對數的 "從樹中移除i，根據情況縮短、分割或洗掉其區間 "也是如此。

事件的形式可以是 "移除B[i]"或 "添加A[i]"。 優先級佇列首先根據添加/減少的元素的大小進行排序，然后將B放在A之前。 (所以我們不會將大小為x的元素放到A中，直到所有大小為x的元素都從B中移除。)

考慮到這一點，我們將把B放在A之前。

考慮到這一點，下面是如何做到這一點的偽代碼。

將所有可能的事件放在優先級佇列中
初始化一個空的區間樹A_tree
初始化一個包含整個范圍的區間樹B_tree
初始化最大區間為（0，-1）（長度為0

對于佇列中的每個事件（型別，i）。
    如果事件.型別=A:
        new_interval = A_tree.add(event.i)
        
        如果事件.i在B_tree中。
            將event.i的A_tree間隔與event.i的B_tree間隔相交
            如果相交的時間長于max_interval。
                更新到新的、更好的max_interval

    否則。
        如果事件.i在A_tree中。
            將事件.i的A樹區間與事件.i的B樹區間相交
            如果相交的時間長于max_interval。
                更新到新的、更好的max_interval

        B_tree.remove(event.i)

處理任何事件都是O(log(n)/code>。有2n = O(n)個事件。所以總體時間是O(n log(n))。