求O(nlogn)时间复杂度最长递减子序列，代码返回递增结果求助

嘿，我来帮你搞定这个问题！你的代码核心逻辑其实是给**最长递增子序列（LIS）**写的，所以才会返回递增的结果，而且比较条件和二分查找的逻辑都需要针对递减序列调整。下面一步步给你拆解问题和修正方案：

问题诊断 #

你的代码现在的问题在于：

1. 比较条件完全搞反：原代码的判断逻辑是维护一个递增的tailTable数组（适配LIS），但我们需要维护一个递减的数组来实现LDS；
2. 二分查找逻辑不匹配：原二分查找是为递增数组设计的，需要调整为适配递减数组的查找逻辑。

修正后的代码 #

下面是调整后的完整代码，我会标注关键修改点：

def binary_search(tail, l, r, key):
    # 适配递减数组的二分查找：找第一个小于key的位置
    while (r - l > 1):
        m = l + (r - l) // 2
        # 原代码是L[m] >= key时调整r，现在改为调整l（因为数组递减）
        if (tail[m] >= key):
            l = m
        else:
            r = m
    return r

def LongestDecreasingSubsequenceLength(L, size):
    if size == 0:
        return 0
    tailTable = [0 for i in range(size + 1)]
    len = 1
    tailTable[0] = L[0]
    
    for i in range(1, size):
        x = L[i]
        # 1. 如果当前元素比tail数组的第一个元素更大：替换起点（能形成更长的递减序列）
        if (x > tailTable[0]):
            tailTable[0] = x
        # 2. 如果当前元素比tail数组最后一个元素更小：直接追加到末尾（延长递减序列）
        elif (x < tailTable[len-1]):
            tailTable[len] = x
            len += 1
        # 3. 否则：找到合适的位置替换，保持tail数组递减性
        else:
            pos = binary_search(tailTable, -1, len-1, x)
            tailTable[pos] = x
    return len

# 测试案例
L = [38, 20, 15, 30, 90, 14, 6, 7]
n = len(L)
print("Length of Longest Decreasing Subsequence is ", LongestDecreasingSubsequenceLength(L, n))
# 输出：Length of Longest Decreasing Subsequence is  5

关键修改说明 #

1. 二分查找函数：
   • 原代码是在递增数组中找第一个>=key的位置，现在调整为在递减数组中找第一个<key的位置，通过修改tail[m] >= key时的指针移动方向实现；
2. 主逻辑条件：
   • 把原代码中替换起点的条件（x < tailTable[0]）改为x > tailTable[0]：因为更大的数作为递减序列的起点，能容纳更多后续更小的元素；
   • 把追加到末尾的条件（x > tailTable[len-1]）改为x < tailTable[len-1]：因为更小的数可以接在当前最长递减序列的末尾，延长序列长度；
3. 增加空数组判断：避免数组为空时的索引错误。

复杂度验证 #

这个实现的时间复杂度确实是O(nlogn)：

• 遍历整个数组的时间是O(n)；
• 每次二分查找的时间是O(logk)（k是当前最长递减子序列的长度，最大为n）；
• 总时间复杂度为O(n * logn)，完全符合你的需求。

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