Pythonで値の範囲の条件を持つ最長のサブリストの長さを見つけるプログラム

numsと呼ばれる数値のリストがあるとすると、最長のサブリストの長さを見つける必要があります。ここで、2 *（サブリストの最小値）>（サブリストの最大値）。

したがって、入力がnums =[10、2、6、6、4、4]のような場合、サブリスト[6、6、4、4]は指定されたものを満たす最長のサブリストであるため、出力は4になります。基準（2 * 4）> 6.

これを解決するには、次の手順に従います-

• ret：=0
• minq：=空の両端キュー
• maxq：=空の両端キュー
• l：=0
• r：=0
• r
• n：=nums [r]
• minqが空ではなく、n
• minqから最後の要素を削除する

例

理解を深めるために、次の実装を見てみましょう-

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