寻找值下降的最长区间：如何优化至亚二次时间复杂度？

给定一组指标数值列表，示例如下：

# 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
[50, 52, 58, 54, 57, 51, 55, 60, 62, 65, 68, 72, 62, 61, 59, 63, 72]

需要找到数值出现下降的最长区间（即存在索引 i < j，使得 values[i] > values[j]，且区间长度 j - i + 1 最大）。上述示例中，最长区间为索引7至14，长度为8。

现有一个时间复杂度为O(n²)的解法：

def get_longest_len(values: list[int]) -> int:
    longest = 0

    for i in range(len(values)-1):
        for j in range(len(values)-1, i, -1):
            if values[i] > values[j] and j - i > longest:
                longest = j - i
                break
    return longest + 1

问：是否存在方法将时间复杂度优化至亚二次级别？

可以通过分治法将问题拆解为子问题求解，将时间复杂度降至O(n log n)（亚二次级别），大幅提升大规模数组下的性能。

核心逻辑 #

1. 拆分递归：将数组从中间分为左右两部分，分别递归计算两部分内部的最长下降区间长度。
2. 跨区间计算：遍历左半部分的每个元素，从右往左在右半部分中找到第一个比它小的元素，记录两者的索引差，以此得到跨区间的最大长度。
3. 合并结果：最终结果取左右子问题结果与跨区间结果的最大值。

代码实现 #

def get_longest_len(values: list[int]) -> int:
    def divide_conquer(left: int, right: int) -> int:
        if left >= right:
            return 0
        
        mid = (left + right) // 2
        # 递归求解左右子区间的最长下降长度
        left_max = divide_conquer(left, mid)
        right_max = divide_conquer(mid + 1, right)
        
        # 计算跨区间的最长下降长度
        cross_max = 0
        for i in range(left, mid + 1):
            j = right
            # 从右往左找第一个比当前左元素小的元素
            while j > mid and values[i] <= values[j]:
                j -= 1
            if j > mid:
                cross_max = max(cross_max, j - i)
        
        return max(left_max, right_max, cross_max)
    
    max_diff = divide_conquer(0, len(values) - 1)
    return max_diff + 1 if max_diff != 0 else 0

复杂度说明 #

• 递归深度为O(log n)，每层递归中跨区间的遍历总时间为O(n)，因此整体时间复杂度为O(n log n)。
• 相比原O(n²)解法，当数组规模超过1000时，性能差距会非常明显。

进阶优化 #

若要进一步降低常数项，可以对跨区间计算做优化：

1. 预处理右半部分的元素，构建一个从右到左的单调递减列表（保存元素值与对应索引）。
2. 对左半部分的每个元素，通过二分查找在单调列表中找到第一个比它小的元素，直接获取最靠右的索引，将跨区间计算的时间从O(n)降至O(n log n)，整体复杂度仍为O(n log n)。

内容的提问来源于stack exchange，提问作者Eugene Yarmash