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 <숫자의 크기인 동안 do
- n :=숫자[r]
- minq가 비어 있지 않고 n
- minq에서 마지막 요소 삭제
minq 끝에 r 삽입
maxq가 비어 있지 않고 n> nums[maxq의 마지막 요소]인 동안 do
- maxq에서 마지막 요소 삭제
maxq 끝에 r 삽입
r :=r + 1
l
minq[0]이 l과 같으면
- minq의 왼쪽 항목
maxq[0]이 l과 같으면
- maxq의 마지막 항목 삭제
l :=l + 1

ret :=ret의 최대값 및 (r - l)

반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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]