在Python中查找具有值范围条件的最长子列表长度的程序

Z时代
2024-01-10
分类：综合

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

所以，如果输入像 nums = [10, 2, 6, 6, 4, 4]，那么输出将是 4，因为子列表 [6, 6, 4, 4] 是满足给定的最长子列表标准 (2*4) > 6。

示例

让我们看看以下实现以获得更好的理解 -

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))