在 Python 中寻找值范围条件下最长子列表长度的程序

在 Python 中寻找值范围条件下最长子列表长度的程序

假设我们有一个名为 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
  • 当 r < nums 的大小时,执行以下操作:
    • n := nums[r]
    • while minq 不是空的 且 n < nums [minq 的最后一个元素],执行以下操作:
      • 从 minq 的末尾删除最后一个元素
    • 在 minq 的末尾添加 r
    • while 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

示例

让我们看一下以下实现,以便更好地理解-

from collections import deque
def solve(nums):
   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

nums = [10, 2, 6, 6, 4, 4]
print(solve(nums))

输入

[10, 2, 6, 6, 4, 4]

输出

4

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程