如何优化求解满足max(A[i:j])<min(B[i:j])的最长连续子数组

核心思路 #

可采用滑动窗口+双单调队列的方案将时间复杂度优化到O(n)，整体思路如下：

• 维护左右两个指针left和right，右指针不断向右扩展窗口边界
• 用两个单调队列分别维护当前窗口[left, right]内数组A的最大值、数组B的最小值，两个队列的队首分别对应当前窗口的A最大值、B最小值，维护操作的摊还时间复杂度为O(1)
• 每次扩展右指针后，检查当前窗口是否满足max(A[left:right]) < min(B[left:right])，如果不满足则不断右移左指针收缩窗口，直到条件成立或窗口为空
• 每次调整完窗口后更新最长符合条件的区间长度即可

代码示例 #

from collections import deque

def longest_valid_interval(A, B):
    n = len(A)
    max_a = deque() # 维护A窗口最大值的单调递减队列
    min_b = deque() # 维护B窗口最小值的单调递增队列
    left = 0
    max_len = 0
    res_interval = []
    for right in range(n):
        # 更新A的最大值队列
        while max_a and A[right] >= A[max_a[-1]]:
            max_a.pop()
        max_a.append(right)
        # 更新B的最小值队列
        while min_b and B[right] <= B[min_b[-1]]:
            min_b.pop()
        min_b.append(right)
        # 收缩左指针直到满足条件
        while max_a and min_b and A[max_a[0]] >= B[min_b[0]]:
            if max_a[0] == left:
                max_a.popleft()
            if min_b[0] == left:
                min_b.popleft()
            left += 1
        # 更新最长长度和对应区间
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
            res_interval = [left+1, right+1] # 转换为题目示例的1-based索引
    return max_len, res_interval

# 测试示例
A = [10, 21, 5, 1, 3]
B = [3, 1, 4, 23, 56]
print(longest_valid_interval(A, B)) # 输出 (2, [4,5]) 与示例结果一致

其他可选方案 #

也可以采用单调栈预处理的方法，先预处理出每个位置i的边界：

• 数组A中i作为最大值的最远左右边界left_a[i]、right_a[i]
• 数组B中i作为最小值的最远左右边界left_b[i]、right_b[i]
  之后遍历每个位置，计算两个边界的交集，统计最长符合条件的区间即可，时间复杂度同样为O(n)。

内容的提问来源于stack exchange，提问作者David jones