用 Python 编写程序，根据给定条件查找最长子列表的长度

pythonserver side programmingprogramming更新于 2026/1/24 0:12:17

假设我们有一个名为 nums 的数字列表，我们必须找到最长子列表的长度，其中 2 * 子列表的最小值 > 子列表的最大值。

因此，如果输入为 nums = [10, 2, 6, 6, 4, 4]，则输出将为 4，因为子列表 [6, 6, 4,4] 是满足条件 2 * 4 > 的最长子列表6.

为了解决这个问题，我们将遵循以下步骤−

ret := 0
定义两个双端队列 minq 和 maxq
l := 0, r := 0
while r < size of nums, do
- n := nums[r]
- while minq and n < nums[minq 的最后一个元素]，执行
  - 从 minq 中删除最后一个元素
- 在 minq 末尾插入 r
- 当 maxq 和 n > nums[maxq 的最后一个元素] 时，执行
  - 从 maxq 中删除最后一个元素
- 在 maxq 末尾插入 r
- r := r + 1
- 当 l < r 和 nums[minq[0]] * 2 <= nums[maxq[0]]，执行
  - 如果 minq[0] 与 l 相同，则
    - 删除 minq 的第一个元素
  - 如果 maxq[0] 与 l 相同，则
    - 删除 maxq 的第一个元素
  - l := l + 1
- ret := ret 和 (r - l) 的最大值
返回 ret

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, nums):
      from collections import deque
      ret = 0
      minq, maxq = deque(), deque()
      l, r = 0, 0
      while r < len(nums):
         n = nums[r]
         while minq and n < nums[minq[-1]]:
            minq.pop()
      minq.append(r)
      while maxq and n > nums[maxq[-1]]:
         maxq.pop()
      maxq.append(r)
      r += 1
      while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
         if minq[0] == l:
            minq.popleft()
         if maxq[0] == l:
            maxq.popleft()
         l += 1
      ret = max(ret, r - l)
   return ret
ob = Solution()
nums = [10, 2, 6, 6, 4, 4]
print(ob.solve(nums))