Pythonで指定された条件で最長のサブリストの長さを見つけるプログラム

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

したがって、入力がnums =[10、2、6、6、4、4]のような場合、サブリスト[6、6、4、4]は基準を保持する最長のサブリストであるため、出力は4になります。 2 *4>6として。

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

• ret：=0

• 2つの両端キューminqとmaxqを定義します

• l：=0、r：=0

• r

  • n：=nums [r]

  • minqとn

    • minqから最後の要素を削除します

  • minqの最後にrを挿入します

  • maxqおよびn>nums[maxqの最後の要素]の場合、実行

    • maxqから最後の要素を削除する

  • maxqの最後にrを挿入します

  • r：=r + 1

  • l

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

入力

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

出力

4