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 :=숫자[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)
리턴 렛

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

예시

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]