Chương trình tìm độ dài của danh sách con dài nhất với điều kiện phạm vi giá trị bằng Python

Giả sử chúng ta có một danh sách các số được gọi là nums, chúng ta phải tìm độ dài của danh sách con dài nhất trong đó 2 * (tối thiểu của danh sách con)> (tối đa của danh sách con).

Vì vậy, nếu đầu vào giống như nums =[10, 2, 6, 6, 4, 4], thì đầu ra sẽ là 4, bởi vì danh sách con [6, 6, 4, 4] là danh sách con dài nhất đáp ứng các điều kiện đã cho tiêu chí (2 * 4)> 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0
• minq:=một hàng đợi kết thúc kép trống
• maxq:=một hàng đợi kết thúc kép trống
• l:=0
• r:=0
• while r
• n:=nums [r]
• trong khi minq không trống và n
• xóa phần tử cuối cùng khỏi minq

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

4