如何识别并移除Python列表中不符合升序的整数？

你的核心问题是相邻元素比较只能处理局部递增逻辑，无法判断某个元素是否会阻断后续更长的递增序列（比如175、659），也无法处理像29这种“回头”的小值。而你期望的结果正好对应原列表的最长递增子序列（Longest Increasing Subsequence, LIS），以下是具体实现思路和代码：

为什么你的原方法不行？ #

你写的相邻比较逻辑只保留了“前一个元素小于后一个元素”的前项，完全没考虑：

• 某个大元素（如175）虽然比前一个大，但后续没有更大的元素能跟上，反而会挡住后面更小但能形成更长序列的元素（如78）
• 像29这种比当前序列最后一个元素小的情况，你的逻辑也没正确过滤掉它

方法1：动态规划（适合理解，小数据量适用） #

动态规划的思路是记录每个位置结尾的最长递增子序列，通过逐个比较前面的元素，找到能形成更长序列的组合，最终取最长的那个子序列：

def longest_increasing_subsequence(nums):
    if not nums:
        return []
    # dp[i] 存储以 nums[i] 结尾的最长递增子序列
    dp = [[num] for num in nums]
    
    for i in range(len(nums)):
        for j in range(i):
            # 如果当前元素比前面的元素大，且能形成更长的子序列
            if nums[i] > nums[j] and len(dp[i]) < len(dp[j]) + 1:
                dp[i] = dp[j] + [nums[i]]
    
    # 返回长度最长的子序列
    return max(dp, key=len)

# 测试你的列表
idx_ls = [24, 175, 78, 80, 659, 126, 141, 149, 29, 158, 178, 179]
print(longest_increasing_subsequence(idx_ls))
# 输出：[24, 78, 80, 126, 141, 149, 158, 178, 179]

方法2：贪心+二分查找（高效，大数据量适用） #

如果你的列表数据量很大，动态规划的O(n²)时间复杂度会不够高效，这时可以用贪心+二分查找的方法，时间复杂度降到O(n log n)：

def longest_increasing_subsequence(nums):
    if not nums:
        return []
    
    # tails[i] 表示长度为 i+1 的递增子序列的最小尾元素
    tails = []
    # prev 记录每个元素在子序列中的前一个元素索引，用于回溯
    prev = [None] * len(nums)
    # indices 记录 tails 中每个元素对应的原数组索引
    indices = []
    
    for i, num in enumerate(nums):
        # 二分查找找到第一个大于等于当前元素的位置
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        # 更新 tails 和对应的索引
        if left == len(tails):
            tails.append(num)
            indices.append(i)
        else:
            tails[left] = num
            indices[left] = i
        
        # 记录当前元素的前一个元素索引
        if left > 0:
            prev[i] = indices[left - 1]
    
    # 回溯构建最终的子序列
    result = []
    current = indices[-1]
    while current is not None:
        result.append(nums[current])
        current = prev[current]
    
    # 反转得到递增顺序
    return result[::-1]

# 测试你的列表
idx_ls = [24, 175, 78, 80, 659, 126, 141, 149, 29, 158, 178, 179]
print(longest_increasing_subsequence(idx_ls))
# 输出：[24, 78, 80, 126, 141, 149, 158, 178, 179]

补充说明 #

如果你只是想要一个任意的递增序列（而非最长），可以用简单的遍历维护当前最大值，但这种方法处理你的列表会得到[24, 175, 659]，显然不符合你的需求，所以最长递增子序列才是正确的方向。

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