如何从数值列表中查找极差小于100的目标连续子序列

从你给出的三组输入输出示例可以发现，实际要找的是列表中最长的、满足区间内最大值与最小值差值小于100的连续子序列——如果只是找任意一段满足条件的序列，输入1里的[1405,1445]、输入3里的[1445,1455]也符合要求，但示例里的输出都是长度最长的那一段合法序列。

核心实现思路 #

• 优先用*滑动窗口（双指针）*方案，相比暴力枚举所有子序列的方法效率高很多，时间复杂度仅为O(n)
• 对于无序列表，用两个单调队列分别维护当前窗口内的最大值、最小值，让窗口内取max、min的操作做到O(1)
• 窗口从左到右逐步扩展右边界，只要窗口内max-min小于100就持续扩展；一旦差值超出阈值，就逐步收缩左边界，直到窗口重新满足差值要求
• 全程记录长度最长的合法窗口的起止位置，最后切片返回结果即可

通用版代码（适配任意无序数值列表） #

from collections import deque

def get_valid_longest_subseq(nums, diff_threshold=100):
    if not nums:
        return []
    # 单调队列分别存储窗口内最大值、最小值的索引
    max_idx_queue = deque()
    min_idx_queue = deque()
    left = 0
    max_valid_len = 0
    best_start, best_end = 0, 0

    for right in range(len(nums)):
        # 维护最大值队列：保证队首是当前窗口的最大值
        while max_idx_queue and nums[max_idx_queue[-1]] <= nums[right]:
            max_idx_queue.pop()
        max_idx_queue.append(right)
        # 维护最小值队列：保证队首是当前窗口的最小值
        while min_idx_queue and nums[min_idx_queue[-1]] >= nums[right]:
            min_idx_queue.pop()
        min_idx_queue.append(right)

        # 窗口差值超阈值时，收缩左边界
        while nums[max_idx_queue[0]] - nums[min_idx_queue[0]] >= diff_threshold:
            left += 1
            # 移除已经落在窗口外的队列元素
            while max_idx_queue[0] < left:
                max_idx_queue.popleft()
            while min_idx_queue[0] < left:
                min_idx_queue.popleft()

        # 更新最长合法窗口的位置
        current_window_len = right - left + 1
        if current_window_len > max_valid_len:
            max_valid_len = current_window_len
            best_start, best_end = left, right

    return nums[best_start:best_end + 1]

针对有序列表的简化实现（适配你给出的示例场景） #

你给出的三组输入列表都是严格从小到大排序的，这类场景下不需要用单调队列维护max和min——因为排序后的连续窗口，最大值一定是窗口最右端的元素，最小值一定是窗口最左端的元素，直接计算两端的差值就能判断是否符合规则，代码更短、运行更快：

def get_valid_subseq_in_sorted_list(nums, diff_threshold=100):
    if not nums:
        return []
    left = 0
    max_len = 0
    best_left, best_right = 0, 0
    for right in range(len(nums)):
        # 有序列表下，窗口max为nums[right]，min为nums[left]
        while nums[right] - nums[left] >= diff_threshold:
            left += 1
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
            best_left, best_right = left, right
    return nums[best_left:best_right + 1]

示例匹配验证 #

把你给出的三组输入代入上述简化版函数测试，输出完全和你的期望结果一致：

• 输入[855, 905, 945, 1405, 1445]，输出[855, 905, 945]
• 输入[855, 905, 915, 945, 1405, 1445]，输出[855, 905, 915, 945]
• 输入[800,955,1030,1045,1445,1455]，输出[955,1030,1045]

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